Страницы

Поиск по вопросам

пятница, 7 июня 2019 г.

Пирамидальная сортировка на C++

Приведите пример пирамидальной сортировки (сортировки кучи) на C++.


Ответ

Сортировка "кучи" на C++. #include
template inline void swap( T & arg1, T & arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; }; template void shiftup(T * a, int size, int indexToShift) { int i = indexToShift; while(i > 1) { if(a[i] < a[i/2]) { swap(a[i], a[i/2]); i /= 2; } else break; } }
template 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(a[i], a[min]); i = min; } else break; } else break; } }
template void heap_sort( T * a, int size) { for (int i = 1; i < size; ++i) shiftup(a, size, i); for (int i = size-1; i > 1; i--) { swap(a[1], a[i]); shiftdown(a, i-1, 1); } }

Комментариев нет:

Отправить комментарий