Викиучебник

Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нормальное форматирование кода на Паскале; языки следуют в алфавитном порядке
Переоформлены функции на Python; добавлен пример кода для проверки их работы
Строка 627:
 
==[[w:Python|Python]]==
Приведённые алгоритмы упорядочивают принимаемую последовательность (список, символьную строку) по неубыванию (''sequence[i] ≤ sequence[i + 1]''). Для упорядочения по невозрастанию (''sequence[i] ≥ sequence[i + 1]'') необходимо заменить все знаки ''<'' на ''> ''в строках, помеченных ''# !''
 
Для большей эффективности вычислений умножение\деление нацело на 2 производятся операторами побитового сдвига влево (''<<'') и вправо (''>>'') соответственно. Например ''parent << 1'' вместо ''parent * 2'', ''length >> 1'' вместо ''length // 2'' и т. п.
 
Проверить работу любой из функций можно добавив, например, следующий код (Python3; для Python2 следует опустить скобки в операторах ''print''):
<source lang="python">
count = 30 # Количество значений в последовательности
# Заполняем последовательность значениями, расположенными в порядке, обратном желаемому:
sequence = list(range(count, 0, -1))
# Для упорядочения по невозрастанию закомментируйте предыдущую строку и раскомментируйте следующую
# sequence = list(range(1, count))
print("Исходная последовательность:")
print(sequence)
heap_sort(sequence)
print("Упорядоченная последовательность:")
print(sequence)
</source>
 
===Вариант № 1===
<source lang="python">
def heapSortheap_sort (lisequence):
"""Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
 
def downHeapsift_down (lisequence, kparent, nend):
new_elemitem = lisequence[kparent]
while 2*k+1 < nTrue:
child = 2*k(parent << 1) + 1
if child+1 <>= n and li[child] < li[child+1]end:
k = child break▼
if child + 1 < end and sequence[child] < sequence[child + 1]: # !
child += 1
if new_elemitem >=< lisequence[child]: # !
sequence[parent] = sequence[child]
parent = child
swap(pi, gtci)else:▼
break
lisequence[kparent] = li[child]item
▲ k = child
li[k] = new_elem
 
sizelength = len(lisequence)
for iindex in range(size//2(length >> 1) - 1, -1, -1):
downHeapsift_down(lisequence, iindex, sizelength)
for iindex in range(sizelength - 1, 0, -1):
sequence[0], sequence[index] = sequence[index], sequence[0]
temp = li[i]
li[i]sift_down(sequence, = li[0], index)
li[0] = temp▼
downHeap(li, 0, i)▼
</source>
 
===Вариант № 2===
<source lang="python">
def heapsortheap_sort (ssequence):
sl = len(s)
 
def swap (piindex1, ciindex2):
if ssequence[piindex1] < ssequence[ciindex2]: # !
ssequence[piindex1], ssequence[ciindex2] = ssequence[ciindex2], ssequence[piindex1]
 
def siftsift_down (piparent, unsortedend):
▲ li[0]while = tempTrue:
i_gt = lambda a, b: a if s[a] > s[b] else b
child = (parent + 1) << 1 # То же, что и parent * 2 + 2
while pi*2+2 < unsorted:
gtciif =child i_gt(pi*2+1,< pi*2+2)end:
if sequence[child] < sequence[child - 1]: # !
▲ swap(pi, gtci)
pi child -= gtci1
swap(parent, child)
# heapify▼
parent = child
for i in range((sl/2)-1, -1, -1):▼
sift(i, sl) else:
# sort break
# Тело функции heap_sort
for i in range(sl-1, 0, -1):▼
length = swaplen(i, 0sequence)
# sift(0, i)Heapifying
▲ for iindex in range(sl(length >> 1) - 1, 0-1, -1):
sift_down(index, length)
▲ # heapifySorting
▲ for iindex in range((sl/2)length - 1, -10, -1):
▲ downHeapswap(liindex, 0, i)
sift_down(0, index)
</source>
 
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Пирамидальная