Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями
Содержимое удалено Содержимое добавлено
Переоформлены функции на Python; добавлен пример кода для проверки их работы |
м →Python: Мелкие поправки к предыдущей правке |
||
Строка 627:
==[[w:Python|Python]]==
Приведённые алгоритмы упорядочивают принимаемую последовательность ''sequence'' (список, символьную строку) по неубыванию (''sequence[i] ≤ sequence[i + 1]''). Для упорядочения по невозрастанию (''sequence[i] ≥ sequence[i + 1]'') необходимо заменить '''все''' знаки ''<'' на ''> ''в строках, помеченных ''# !''
Для большей эффективности вычислений умножение\деление нацело на 2 производятся операторами побитового сдвига влево (''<<'') и вправо (''>>'') соответственно. Например ''parent << 1'' вместо ''parent * 2'', ''length >> 1'' вместо ''length // 2'' и т. п.
Строка 649:
def heap_sort (sequence):
def sift_down (
item = sequence[parent]
while True:
Строка 663:
break
sequence[parent] = item
# Тело функции heap_sort
length = len(sequence)
# Формирование первичной пирамиды
for index in range((length >> 1) - 1, -1, -1):
sift_down(
# Окончательное упорядочение
for index in range(length - 1, 0, -1):
sequence[0], sequence[index] = sequence[index], sequence[0]
sift_down(
</source>
Строка 692 ⟶ 694 :
# Тело функции heap_sort
length = len(sequence)
# Формирование первичной пирамиды
for index in range((length >> 1) - 1, -1, -1):
sift_down(index, length)
# Окончательное упорядочение
for index in range(length - 1, 0, -1):
swap(index, 0)
| |||