I tried to optimize heap sort algorithm. Instead of recursion, I used iteration:
void max_heapify (int arr[], int heapsize, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
do {
if (i != largest) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
i = largest;
left = 2 * i;
right = 2 * i + 1;
}
if (left < heapsize && arr[largest] < arr[left])
largest = left;
if (right < heapsize && arr[largest] < arr[right])
largest = right;
} while (i != largest);
}
void heap_sort (int arr[], int size) {
int i;
for (i = size / 2 - 1; i >= 0; i--)
max_heapify(arr, size, i);
for (i = size - 1; i > 0; i--) {
int tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
max_heapify (arr, i, 0);
}
}
Seems like it's ok, but is there way to improve it?