Как изменить пирамидальну сортировку?

Question

void heapify(int arr[], int n, int i)
{
    int largest = i;   
    int l = 2*i + 1; // левый = 2*i + 1
    int r = 2*i + 2; // правый = 2*i + 2
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
 
        heapify(arr, n, largest);
    }
}
 
void heapSort(int arr[], int n)
{
 
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    for (int i=n-1; i>=0; i--)
    {
        swap(arr[0], arr[i]);
 
        heapify(arr, i, 0);
    }
}

Добрый день, хочу задать вот такой вопрос: вот код пирамидального сортировки, а как его можно изменить так, чтобы в первой функции не было рекурсии и можно именно пирамидальное сортировки в одной функции.Ну или хотелось б упрощенний вариант.Буду благодарен за помощь

Answer 1

Вот так можно:

void sift(int *numbers, int root, int bottom) {
    int maxChild;
    bool done = false;
    while ((root * 2 <= bottom) && (!done)){
        maxChild = ((root*2 == bottom) ||(numbers[root*2] > numbers[root*2+1])) ? root*2 : root*2+1
        if (numbers[root] < numbers[maxChild]){
            std::swap(numbers[root], numbers[maxChild]);
            root = maxChild;
        }
        else
            done = true;
    }
}

void heapSort(int *numbers, int array_size){
    for (int i = (array_size / 2); i >= 0; --i)
        sift(numbers, i, array_size - 1);
    for (int i = array_size-1; i >= 1; --i){
        std::swap(numbers[0], numbers[i])
        sift(numbers, 0, i-1);
    }
}

БЛОГ НА HUSL

Как изменить пирамидальну сортировку?

Ответы (1 шт):