Quicksort return unsorted array

Question

У меня есть два дня, пытаясь понять, почему моя функция quicksort возвращает все, кроме двух элементов, отсортированных в правильном порядке.

с входным

quicksort([0,7,3,11,23,87,999,1023,12,713,5,6,9]) 

Выходы

[0, 6, 3, 5, 7, 9, 11, 12, 23, 87, 713, 999, 1023] 

Что вы думаете, это неправильно с функцией?

def quicksort(array): 
    #Base case 
    if len(array) <= 1: 
     return array 
    #Choose pivot always at the left part and partition array around it 
    Pivot = partition(array,0,len(array)); 
    #Add values for left and righ arrays 
    left = array[:Pivot] 
    right = array[Pivot+1:] 
    #Add recursive calls 
    left = quicksort(left) 
    right = quicksort(right) 
    #Append Pivot at the end of left array 
    left.append(array[Pivot]) 
    return left+right 

По вопросам завершения я добавляю функцию перегородки, но я почти уверен, что проблемы там нет.

def partition(array,left,right): 
    #If pivot is not on leftmost, swap to make it leftmost 
    Pivot = array[left] 
    i = left+1 
    for j in range(left+1,right): 
     if array[j] < Pivot: 
      #Swap array[j] and array[i] 
      array[j], array[i] = array[i], array[j] 
      i += 1; 
    #Swap pivot and A[i-1]   
    array[left], array[i-1] = array[i-1], array[left] 
    return left 

Answer 1

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

Answer 2

Только ради завершения, используя списки понимания pythons, значительно упрощается реализация кода и его чтение.

def qs(l): 
    if len(l) < 2: 
     return l 
    pivot = l.pop() 
    left = [x for x in l if x < pivot] 
    right = [x for x in l if x >= pivot] 
    return qs(left) + [pivot] + qs(right) 

Это очень похоже на псевдокод в текстовых книгах.

1. Списки размера 1 или 0 сортируются по определению
2. Выберите Pivot. В данном случае это последний элемент
3. создать два раздела так, что один имеет все элементы, меньшие, чем стержень, а другой имеет элементы больше или равен поворотной
4. рекурсивный вызов быстрой сортировки на обоих разделов и добавить результаты с точкой поворота в середине