quick sort python recursion

Question

Это мой быстрый код сортировки, функция partition работает хорошо, но у меня возникла проблема при вызове рекурсии. pos изменяется каждый раз, когда он запускает функцию, а затем лимиты списка также изменяются. Как это исправить?

def partition(lst, start, end): 

    pos=0 
    if len(lst)<2: 
     return 
    for i in range(len(lst[start:end])): 
     if lst[i] < lst[end]: 
      lst[i],lst[pos]=lst[pos],lst[i] 
      pos+=1 

     elif i==(len(lst[start:end])-1): 
      lst[end],lst[pos]=lst[pos],lst[end] 

    return pos 

def quick_sort_recursive(lst, start, end): 

     pos=partition(lst, start, end) 
    if start<=pos<=end : 
     quick_sort_recursive(lst, start, pos-1) 
     quick_sort_recursive(lst, pos+1, end) 
    else: 
     return lst 

Answer 1

Есть многочисленные проблемы в вашем коде, вот некоторые исправляет только, чтобы сделать его работу:

def partition(lst, start, end): 
    pos = start       # condition was obsolete, loop won't 
              # simply run for empty range 

    for i in range(start, end):   # i must be between start and end-1 
     if lst[i] < lst[end]:    # in your version it always goes from 0 
      lst[i],lst[pos] = lst[pos],lst[i] 
      pos += 1 

    lst[pos],lst[end] = lst[end],lst[pos] # you forgot to put the pivot 
              # back in its place 
    return pos 

def quick_sort_recursive(lst, start, end): 
    if start < end:      # this is enough to end recursion 
     pos = partition(lst, start, end) 
     quick_sort_recursive(lst, start, pos - 1) 
     quick_sort_recursive(lst, pos + 1, end) 
              # you don't need to return the list 
              # it's modified in place 

Пример:

example = [3,45,1,2,34] 
quick_sort_recursive(example, 0, len(example) - 1) 
print example 

Дает:

python test.py

[1, 2, 3, 34, 45]

Answer 2

тривиальный пример алгоритма быстрой сортировки:

*

### QUICKSORT 
A=[44,5,22,0,323,995,94,4,7,15] 
def main(): 
    r=len(A)-1 
    p=0 
    Result=QuickSort(A,p,r) 
    print(Result) 
def QuickSort(A,p,r): 

    if p<r: 
     q=partition(A, p, r) 
     QuickSort(A, p, q-1) 
     QuickSort(A, q+1, r) 
    return A 
def partition(A,p,r): 
    x=A[r] 
    i=p-1 
    for j in range(p,r): 
     if A[j]<=x: 
      i=i+1 
      a,b=A.index(A[i]), A.index(A[j]) 
      A[a],A[b]=A[b],A[a] 
    d,c=A.index(A[i+1]),A.index(A[r]) 
    A[c],A[d]=A[d],A[c] 
    return i+1 
main() 

*