В соответствии с псевдокодом, представленным на многих веб-сайтах, я написал этот алгоритм секционирования Хоара, который принимает массив, начальный и конечный индексы подмассива для разделения на основе заданного опорного элемента. Он работает нормально, но может ли кто-нибудь объяснить логику, как он делает то, что делает? Вот код:
Код: Выделить всё
def hoare(arr,start,end):
pivot = 4
i,j = start,end
while i < j:
while i < j and arr[i] = i and arr[j] > pivot:
j -= 1
if i < j:
arr[i],arr[j] = arr[j],arr[i]
return j
Есть еще один вариант разделения — алгоритм Ломуто. Он делает что-то похожее, хотя, поскольку я вообще не понимаю алгоритм Хоара, я не могу заметить разницу. Может ли кто-нибудь объяснить, что происходит в алгоритме, и какой из них в каком случае дает лучшую производительность?
Подробнее здесь:
https://stackoverflow.com/questions/125 ... -algorithm
Мобильная версия