Быстрая сортировка по Python с использованием одной переменной для ввода функции

Question

Я знаю, что люди скажут, что это дубликат, но код, который я нашел, не работает, и я понятия не имею, как его исправить, так что это не дубликат, потому что я спрашиваю, как исправить МОЙ код, а не делать Сама проблема. Вот код:

def partition(array, start, end):
  pivot = array[start]
  low = start + 1
  high = end
  while True:
    while low <= high and array[high] >= pivot:
        high = high - 1
    while low <= high and array[low] <= pivot:
       low = low + 1
    if low <= high:
      array[low], array[high] = array[high], array[low]
    else:
      break
  array[start], array[high] = array[high], array[start]
  return high
def qsort(array):
  start = min(array)
  end = max(array)
  if start >= end:
    return
  p = partition(array, start, end)
  qsort(array, start, p-1)
  qsort(array, p+1, end)

Каждый раз, когда я пытаюсь его использовать, я получаю крэ sh. Я сделал qsort функцией с одной переменной, затем установил конец в max, а начало в min. Cra sh, который я получаю, когда пытаюсь использовать его, говорит следующее:

qsort([1,5,1,6])
>>>Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "main.py", line 88, in qsort
    p = partition(array, start, end)
  File "main.py", line 73, in partition
    while low <= high and array[high] >= pivot:
IndexError: list index out of range

Я знаю, это означает, что я превысил максимум или имел переполнение стека (смеется), но я не уверен, как это исправить это в моем коде. Помощь!

Answer 1

Код нуждается в функции ввода или изменении в вызывающем коде, чтобы использовать рекурсивную функцию с параметрами start и end

def partition(array, start, end):
  pivot = array[start]
  low = start + 1
  high = end
  while True:
    while low <= high and array[high] >= pivot:
        high = high - 1
    while low <= high and array[low] <= pivot:
       low = low + 1
    if low <= high:
      array[low], array[high] = array[high], array[low]
    else:
      break
  array[start], array[high] = array[high], array[start]
  return high

def qsortr(array, start, end):          # recursive function
  if start >= end:
    return
  p = partition(array, start, end)
  qsortr(array, start, p-1)
  qsortr(array, p+1, end)

def qsort(array):                       # entry function
  qsortr(array, 0, len(array)-1);       # fix

A = [1,5,1,6]
qsort(A)
print(A)

альтернативный тестовый код для сортировки 512K ints

import random
from time import time
# test sort
a = [random.randint(0, 2147483647) for r in xrange(512*1024)]
s = time()
qsort(a)
e = time()
print e - s

# check to see if data was sorted
f = 0
for i in range (1, len(a)):             # use xrange for python 2.x
    if(a[i-1] > a[i]):
        f = 1
        break
if(f == 0):
    print("sorted")
else:
    print("error")

Answer 2

Помимо логики c, я могу видеть из вашего кода, что ваши start и end содержат значения массива, это должны быть индексы. start следует инициализировать как 0 и end как len(array)-1