Программа Python-Quicksort на месте

Question

У меня здесь есть программа быстрой сортировки, но, похоже, проблема с результатом. Я думаю, что, должно быть, была проблема в областях, выделенных ниже, когда ссылаются на некоторые значения. Какие-либо предложения?

#where l represents low, h represents high 
def quick(arr,l,h): 
    #is this the correct array for quicksorting? 
    if len(x[l:h]) > 1: 
     #r is pivot POSITION 
     r = h 
     #R is pivot ELEMENT 
     R = arr[r] 
     i = l-1 
     for a in range(l,r+1): 
      if arr[a] <= arr[r]: 
       i+=1 
       arr[i], arr[a] = arr[a], arr[i] 
     #should I take these values? Note that I have repeated elements below, which is what I want to deal with 
     quick(arr,l,arr.index(R)-1) 
     quick(arr,arr.index(R)+arr.count(R),h) 

x = [6,4,2,1,7,8,5,3] 

quick(x,0,len(x)-1) 

print(x) 

Answer 1

Пожалуйста, проверьте это. Думаю, ты находишь свой ответ.

def partition(array, begin, end): 
    pivot = begin 
    for i in xrange(begin+1, end+1): 
     if array[i] <= array[begin]: 
      pivot += 1 
      array[i], array[pivot] = array[pivot], array[i] 
    array[pivot], array[begin] = array[begin], array[pivot] 
    return pivot 


def quicksort(array, begin=0, end=None): 
    if end is None: 
     end = len(array) - 1 
    if begin >= end: 
     return 
    pivot = partition(array, begin, end) 
    quicksort(array, begin, pivot-1) 
    quicksort(array, pivot+1, end) 

array = [6,4,2,1,7,8,5,3] 
quicksort(array) 
print (array) 

Answer 2

 #should I take these values? Note that I have repeated elements below, which is what I want to deal with 
     quick(arr,l,arr.index(R)-1) 
     quick(arr,arr.index(R)+arr.count(R),h) 

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

Чтобы сделать это предположение, разделите на три вместо двух групп, как описано at Wikipedia.