Программирование на языке Pascal




Пирамидальная сортировка - часть 3


1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12]; 2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12]; 3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12]; 4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12]; 5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12]; 6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12]; 7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12]; 8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12]; 9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12]; 10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12]; 11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12]; 12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12]; 13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12]; 14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12]; 15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12]; 16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12]; 17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12]; 18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12]; 19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12]; 20) Просеивать уже ничего не нужно; 21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12]; 22) Просеивать ничего не нужно, сортировка закончена.

Эффективность алгоритма УлПир

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.




Содержание  Назад  Вперед