<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Пирамидальная сортировка
Исходник: Пирамидальная сортировка, балансировка пирамиды, просеивание элементов через пирамиду [C++, code #29, hits: 11315, рейтинг: 3/4,4.79(2987)] +
автор: 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)
Расход памяти: - (только счетчики цикла, доп. переменные, вызов функции балансировки)

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.002723 секунд
Количество запросов к БД: 7, gzip: 3.8kb/13.3kb(72%)