воскресенье, 5 сентября 2010 г.

Пирамидальная сортировка (Heap Sort)

[Все сортировки]

Теория: читаем дивную статью с картинками

Практика
: informatics.mccme.ru

Визуализатор: rain.ifmo.ru [Java]

Реализация
:
Общую логику программы можно отследить по этому фрагменту кода:

  1. // просейка вверх узла с индексом pos
  2. void shiftUp(vector<int> &mas, int pos)
  3. {
  4.   while (!isRoot(pos) && mas[pos]>mas[Parent(pos)])
  5.   {
  6.     swap(mas[pos],mas[Parent(pos)]);
  7.     pos = Parent(pos);
  8.   }
  9. }
  10. // просейка вниз узла с индексом pos
  11. void shiftDown(vector<int> &mas, int pos, int n)
  12. {
  13.   while (!isList(pos,n))
  14.   {
  15.     int posMaxChild = Left(pos);
  16.     if (isRightExist(pos,n))
  17.     {
  18.       if (mas[Left(pos)] < mas[Right(pos)])
  19.         posMaxChild = Right(pos);
  20.     }
  21.     if (mas[pos]<mas[posMaxChild])
  22.     {
  23.       swap(mas[pos],mas[posMaxChild]);
  24.       pos = posMaxChild;
  25.     }
  26.     else
  27.       break;
  28.   } 
  29. }
  30. // преобразовать входной массив в кучу
  31. void make_heap(vector<int> &mas)
  32. {
  33.   for (int i=1;i<mas.size();i++)
  34.     shiftUp(mas,i);
  35. }
  36. // упорядочивание входного массива пирамидальной сортировкой
  37. void heap_sort(vector<int> &mas)
  38. {
  39.   make_heap(mas);
  40.   int size = mas.size();
  41.   for (int i=0;i<mas.size();i++)
  42.   {
  43.     swap(mas[0],mas[size-1]);
  44.     size--;
  45.     shiftDown(mas,0,size);
  46.   }
  47. }
* This source code was highlighted with Source Code Highlighter.
Полный исходник глядим здесь

Для учебных целей можно рассмотреть рекурсивную, более понятную запись функций shiftDown и shiftUp:

  1. // просейка вверх
  2. void shiftUp(vector<int> &mas, int pos)
  3. {
  4.   if (isRoot(pos))
  5.     return;
  6.   if (mas[Parent(pos)] < mas[pos])
  7.   {
  8.     swap(mas[Parent(pos)],mas[pos]);
  9.     shiftUp(mas,Parent(pos));
  10.   }
  11. }
  12. // просейка вниз
  13. void shiftDown(vector<int> &mas, int pos, int n)
  14. {
  15.   if (isList(pos,n))
  16.     return;
  17.   int posMaxChild = Left(pos);
  18.   if (isRightExist(pos,n))
  19.   {
  20.     if (mas[Left(pos)] < mas[Right(pos)])
  21.       posMaxChild = Right(pos);
  22.   }
  23.   if (mas[pos]<mas[posMaxChild])
  24.   {
  25.     swap(mas[pos],mas[posMaxChild]);
  26.     shiftDown(mas, posMaxChild,n);
  27.   }
  28. }
* This source code was highlighted with Source Code Highlighter.

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

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