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:])

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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