Быстрая сортировка - реализация CLRS в python

Question

Я пытаюсь реализовать быструю сортировку в python. Версия для печати CLRS.

Вот что я написал. Я думаю, что он работает отлично по большей части, за исключением средних элементов списка.

Может кто-нибудь помочь?

#! /usr/bin/python 

#quick sort 

def swap(array,i,j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 

def partition(array, start,end): 
    x = array[end] 
    i = start -1 
    for j in xrange(start+1, end): 
     if (array[j] <= x): 
      i = i+1 
      swap (array,i,j) 
     swap(array,i+1,end) 
    return i+1 

def quicksort(array,p,r): 
    if p<r: 
     q = partition(array,p,r) 
     quicksort(array,p,q-1) 
     quicksort(array,q+1,r) 

def main(): 
    unsortedArray = [2,8,7,1,3,5,6,4,9,0] 
    quicksort(unsortedArray,0,len(unsortedArray)-1) 
    print unsortedArray 


if __name__ == '__main__': 
    main() 

Вывод должен быть [0,1,2,3,4,5,6,7,8,9] .Instead время печати [2, 0, 3, 4, 1, 6, 5, 7, 9, 8].

Answer 1

Согласно псевдокоде я нашел на https://users.cs.fiu.edu/~giri/teach/5407/F08/Lec7.pdf, ваша реализация partition является неправильным, потому что

swap(array,i+1,end) 

должны НЕ выполняться в каждой итерации, но вместо этого только один раз в функции.

Я переписал это так:

def partition(array, start,end): 
    x = array[end] 
    i = start -1 
    for j in xrange(start, end): 
     if (array[j] <= x): 
      i = i+1 
      swap (array,i,j) 
    swap(array,i+1, end) 
    return i+1 

и она отлично работает.