Никак не могу понять принцип работы алгоритма быстрой сортировки. Единственное что могу реализовать это данную версию quicksort:
def qsort(array):
if len(array) <= 1:
return array
middle_elem = array[(len(array) - 1) // 2]
smallest = []
middlest = []
largest = []
for i in array:
if i < middle_elem:
smallest.append(i)
elif i > middle_elem:
largest.append(i)
else:
middlest.append(i)
return qsort(smallest) + middlest + qsort(largest)
Есть более быстрая и выгодная по памяти ее версия, но именно она у меня и не работает!
def qqsort(array):
if len(array) <= 1:
return array
l = 0
r = len(array) - 1
mid = (l + r) // 2
while l <= r:
while array[l] < array[mid]:
l += 1
while array[r] > array[mid]:
r -= 1
if l <= r:
array[r], array[l] = array[l], array[r]
l += 1
r -= 1
return qqsort(array[:l]) + qqsort(array[r:])
Почему - так и не понял.