0

Никак не могу понять принцип работы алгоритма быстрой сортировки. Единственное что могу реализовать это данную версию 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:])

Почему - так и не понял.

3
  • А что не работает? Какие симптомы? 24 фев 2021 в 18:54
  • зачем вам во втором случае вообще нужен mid? Ведь, что l, что r, могут пересечь его и тогда ваши первые 2 while цикла потеряют всякий смысл.
    – tym32167
    24 фев 2021 в 19:02
  • Зачем вообще реализовывать алгоритмы сортировки в пайтон? Думаете быстрее чем на Си получится?)))
    – alex
    24 фев 2021 в 20:10

1 ответ 1

0

А так?

def qqsort(array):
    if len(array) <= 1:
        return array

    l = 0
    r = len(array) - 1
    pivot = array[(l + r) // 2]

    while l <= r:
        while array[l] < pivot:
            l += 1
        while array[r] > pivot:
            r -= 1
        if l <= r:
            array[r], array[l] = array[l], array[r]
            l += 1
            r -= 1

    return qqsort(array[:l]) + qqsort(array[l:])

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.