Ошибка при выборе элемента средней точки в python quick sort

Question

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

Вот код.

def qsort(l,start,end): 

    if start >= end : 
     return 
    i,j = start, end 
    pivot = (start + (end - start)/2)  

    while i<=j: 
     while(l[i] < l[pivot]): 
      i+=1 
     while(l[j] > l[pivot]): 
      j-=1 
     if(i<=j): 
      l[i],l[j] = l[j],l[i] 
      i+=1 
      j-=1 

    qsort(l,start,j) 
    qsort(l,i,end) 

    return l 

    a = [67,89,45,23,15,19,1,14,100] 
    print qsort(a,0,len(a)-1) 

Выход указанного выше кода [1, 14, 15, 23, 19, 45, 67, 89, 100]. По некоторым причинам позиции 23 и 19 не меняются местами.

Однако, если я выбираю случайный стержень с оператором pivot = random.randint (fst, lst), я получаю полностью отсортированный список. Может ли кто-нибудь объяснить причину этого?

Answer 1

Вы можете найти эти справочные реализации полезными, пытаясь понять свои собственные.

---

Возвратившись новый список:

def qsort(array): 
    if len(array) < 2: 
     return array 
    head, *tail = array 
    less = qsort([i for i in tail if i < head]) 
    more = qsort([i for i in tail if i >= head]) 
    return less + [head] + more 

---

Сортировка списка в месте:

def quicksort(array): 
    _quicksort(array, 0, len(array) - 1) 

def _quicksort(array, start, stop): 
    if stop - start > 0: 
     pivot, left, right = array[start], start, stop 
     while left <= right: 
      while array[left] < pivot: 
       left += 1 
      while array[right] > pivot: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -= 1 
     _quicksort(array, start, right) 
     _quicksort(array, left, stop) 

---

Создания отсортированы элементы из итератора:

def qsort(sequence): 
    iterator = iter(sequence) 
    head = next(iterator) 
    try: 
     tail, more = chain(next(iterator), iterator), [] 
     yield from qsort(split(head, tail, more)) 
     yield head 
     yield from qsort(more) 
    except StopIteration: 
     yield head 

def chain(head, iterator): 
    yield head 
    yield from iterator 

def split(head, tail, more): 
    for item in tail: 
     if item < head: 
      yield item 
     else: 
      more.append(item)