Быстрое сортирование массива cType чисел

Question

Я пытаюсь реализовать пару методов сортировки в массиве ctypes целых чисел в Python 3 и, похоже, не может определить метод Quicksort. Я считаю, что большая часть моего кода верна, но мне просто не хватает глупого заявления. Прямо сейчас все, что я получаю, когда пытаюсь напечатать массив, который возвращается, является объектом «NoneType».

Большое спасибо.

#Quicksort Algorithm 
def quicksort(list): 
    n = len(list) 
    return recquick(list, 0, n-1) 

#Recursive Quicksort Function 
def recquick(list, first, last): 
    #Base Case 
    if first >= last: 
     return 
    else: 
     #Save pivot value 
     pivot = list[first] 

     pos = partseq(list, first, last) 

     #Repeat the process on the two subsequences 
     recquick(list, first, pos-1) 
     recquick(list, pos+1, last) 

#Partitions subsequence using first key as pivot 
def partseq(list, first, last): 
    #Save pivot value 
    pivot = list[first] 

    #Find pivot position and move elements around the pivot 
    left = first + 1 
    right = last 
    while left <= right: 
     #Find the first key larger than the pivot 
     while left < right and list[left] < pivot: 
      left += 1 

     #find the last key in the sequence that is smaller than the pivot 
     while right >= left and list[right] >= pivot: 
      right -= 1 


     #Swap the two keys 
     if left < right: 
      tmp = list[left] 
      list[left] = list[right] 
      list[right] = tmp 

     #Put the pivot in the proper position 
     if right != first: 
      list[first] = list[right] 
      list[right] = pivot 

     #Return index position of the pivot value 
     return right 

Answer 1

Ваш внешний цикл while не соответствует partseq. Перемещение справа и поворота должно происходить только один раз за пределами цикла while. Ответное заявление должно быть вне времени

Также на основе This link, я сделал небольшие изменения в алгоритм

• left начинается в first
• первый внутренний, а цикл выполняется до list[left] <= pivot и второго внутреннего в то время как цикл выполняется до list[right] > pivot

#Quicksort Algorithm 
def quicksort(list): 
    n = len(list) 
    return recquick(list, 0, n-1) 

#Recursive Quicksort Function 
def recquick(list, first, last): 
    #Base Case 
    if first >= last: 
     return 
    else: 
     #Save pivot value 
     pivot = list[first] 

     pos = partseq(list, first, last) 

     #Repeat the process on the two subsequences 
     recquick(list, first, pos-1) 
     recquick(list, pos+1, last) 

#Partitions subsequence using first key as pivot 
def partseq(list, first, last): 
    #Find pivot position and move elements around the pivot 
    pivot = list[first] 

    left = first 
    right = last 
    while left<right: 
     #Find the first key larger than the pivot 

     while left < right and list[left] <= pivot: 
      left += 1 

     #find the last key in the sequence that is smaller than the pivot 
     while right >= left and list[right] > pivot: 
      right -= 1 

     #Swap the two keys 
     if left < right: 
      tmp = list[left] 
      list[left] = list[right] 
      list[right] = tmp 


    #Put the pivot in the proper position 
    #right to left 
    if right != first: 
     list[first] = list[right] 
     list[right] = pivot 

    #Return index position of the pivot value 
    return right 

Результат

>>> import try1 
>>> a=[1,2,3,4,5,6,] 
>>> try1.quicksort(a) 
>>> a 
[1, 2, 3, 4, 5, 6] 
>>> a=[6,5,4,3,2,1,] 
>>> try1.quicksort(a) 
>>> a 
[1, 2, 3, 4, 5, 6] 
>>> a=[1] 
>>> try1.quicksort(a) 
>>> a 
[1] 
>>> a=[] 
>>> try1.quicksort(a) 
>>> a 
[] 
>>> a=[43,76,9,10,1,15,62,] 
>>> try1.quicksort(a) 
>>> a 
[1, 9, 10, 15, 43, 62, 76]