Pyramid sorting in C++

Question

Pyramid sorting in C++

Give an example of pyramid sorting (heap sorting) in C++.

3

c++алгоритм сортировка

Author: Nicolas Chabanovsky, 2010-10-20

Source

2 answers

C++ already has functions for working with the heap - std::make_heap and std::sort_heap, for this reason, heap sorting is implemented trivially:

template<typename RandomAccessIter, typename Compare = std::less<>>
void heap_sort(RandomAccessIter first, RandomAccessIter last, Compare cmp = Compare{}) {
    std::make_heap(first, last, cmp);
    std::sort_heap(first, last, cmp);
}

1

Author: Abyx, 2016-01-17 12:06:10

score 3 · Accepted Answer

Sorting the "heap" in C++.

#include <vector>

template <typename T>
inline void swap( T & arg1, T & arg2)
{
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
};
template <typename T>
void shiftup(T * a, int size, int indexToShift) {
    int i = indexToShift;
    while(i > 1) {
        if(a[i] < a[i/2]) {
            swap<T>(a[i], a[i/2]);
            i /= 2;
        } else
            break;
    }
}

template <typename T>
void shiftdown(T * a, int size, int indexToShift) {
    int i = indexToShift;
    int min;
    while ( i < size) {
        if ( i*2 <= size) {
            if (i*2+1 <= size) {
                min = a[i*2] < a[i*2+1] ? i*2 : i*2+1;
            } else 
                min = i*2;
            if (a[i] > a[min]) {
                swap<T>(a[i], a[min]);
                i = min;
            } else
                break;
        } else 
            break;
    }
}

template <typename T> 
void heap_sort( T * a, int size) {
    for (int i = 1; i < size; ++i) 
        shiftup<T>(a, size, i);
    for (int i = size-1; i > 1; i--) {
        swap<T>(a[1], a[i]);
        shiftdown<T>(a, i-1, 1);
    }
}