Задача: Сравнение алгоритмов сортировки массива
Исходник: PyramidSort.cpp, язык: C++ [code #34, hits: 12399]
автор: this [добавлен: 17.02.2006]
  1. #include "PyramidSort.h"
  2.  
  3. PyramidSort::PyramidSort(int n, int* x) : Sort(n, x) {
  4. this->algName = "Pyramid Sort";
  5. }
  6.  
  7. void PyramidSort::Screening(int k, int end) {
  8.  
  9. /* Это чтобы при k=0 и n=0 не делалось лишней
  10. перестановки*/
  11. if (0 == end) return;
  12.  
  13. int tmp;
  14. int childPos;
  15. tmp = this->x[k];
  16.  
  17. while (k <= end/2) {
  18. childPos = 2*k; // Левый ребенок элемента k
  19.  
  20. /* выбираем большего ребенка элемента k
  21. из 2-х: либо левый, либо правый
  22. */
  23. if (childPos < end && this->x[childPos] < this->x[childPos + 1]) {
  24. childPos++;
  25. }
  26. /* Если родитель x[k] больше всех своих детей,
  27. то ничего не делаем, он стоит на правильном месте */
  28. if(tmp >= this->x[childPos]) break;
  29.  
  30. // иначе - меняем x[k] с наибольшим ребенком
  31. this->x[k] = this->x[childPos];
  32. k = childPos;
  33. this->CountSwap();
  34. }
  35. this->x[k] = tmp; this->CountSwap();
  36. }
  37.  
  38. void PyramidSort::Run(void) {
  39. int i;
  40. int tmp;
  41.  
  42. // Построение пирамиды
  43. for (i = this->n/2; i >= 0; i--) {
  44. this->Screening(i, (this->n - 1));
  45. }
  46.  
  47. /* Формирование конечной отсортированной
  48. последовательности + "балансирование"
  49. пирамиды */
  50. for (i = this->n - 1; i > 0; i--) {
  51. // меняем первый с последним
  52. this->Swap(0, i);
  53.  
  54. /* Восстановление баланса
  55. для пирамиды x[0..i-1] */
  56. this->Screening(0, i-1);
  57. }
  58. }
  59.  
  60. PyramidSort::~PyramidSort(void)
  61. {
  62. }
Реализация класса пирамидальной сортировки.

Заголовочный файл: PyramidSort.h
Функция-аналог: тут
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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