Задача: Пирамидальная сортировка
Исходник: Пирамидальная сортировка, язык: C++ [code #29, hits: 15909]
автор: this [добавлен: 05.02.2006]
  1. /* Функция "балансировки" пирамиды.
  2. (просеивания, добавления элементов) */
  3. template<class T>
  4. void Screening(T* x, int k, int n) {
  5. /* Это чтобы при k=0 и n=0 не делалось лишней
  6. перестановки*/
  7. if (0 == n) return;
  8.  
  9. T tmp;
  10. int childPos;
  11. tmp = x[k];
  12.  
  13. while (k <= n/2) {
  14. childPos = 2*k; // Левый ребенок элемента k
  15.  
  16. /* выбираем большего ребенка элемента k
  17. из 2-х: либо левый, либо правый
  18. */
  19. if (childPos < n && x[childPos] < x[childPos + 1]) {
  20. childPos++;
  21. }
  22. /* Если родитель x[k] больше всех своих детей,
  23. то ничего не делаем, он стоит на правильном месте */
  24. if(tmp >= x[childPos]) break;
  25.  
  26. // иначе - меняем x[k] с наибольшим ребенком
  27. x[k] = x[childPos];
  28. k = childPos;
  29. }
  30. x[k] = tmp;
  31. }
  32.  
  33. template<class T>
  34. void PyramidSort1(T* x, int n) {
  35. int i;
  36. T tmp;
  37.  
  38. // Построение пирамиды
  39. for (i = n/2; i >= 0; i--) {
  40. Screening(x, i, n-1);
  41. }
  42.  
  43. /* Формирование конечной отсортированной
  44. последовательности + "балансирование"
  45. пирамиды */
  46. for (i = n-1; i > 0; i--) {
  47. // меняем первый с последним
  48. swap(x, 0, i);
  49.  
  50. /* Восстановление баланса
  51. для пирамиды x[0..i-2] */
  52. Screening(x, 0, i-1);
  53. }
  54. }
Как видно, алгоритм разбит на 2 важные задачи: функция балансировки пирамиды и собственно сама сортировка.

Производительность: ~O(n*log n)
Расход памяти: - (только счетчики цикла, доп. переменные, вызов функции балансировки)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию