Quicksort в python3. Last Pivot

Question

Спасибо, что нашли время, чтобы прочитать это :) Я реализую свою собственную версию быстрой сортировки в python, и я пытаюсь заставить ее работать с некоторыми ограничениями из предыдущего школьного задания. Обратите внимание, что причины, по которым я избежал использования IN, - это то, что он не был разрешен в проекте, над которым я работал (не знаю, почему: 3).

он отлично работал для целых чисел и строк, но я не могу его адаптировать для своего CounterList(), который представляет собой список узлов, содержащих произвольное целое число и строку в каждом, даже если я только сортирую по целым числам, содержащимся в эти узлы.

Pastebins:

• Мой QuickSort: http://pastebin.com/mhAm3YYp.
• CounterList и CounterNode, код. http://pastebin.com/myn5xuv6.

---

from classes_1 import CounterNode, CounterList 

def bulk_append(array1, array2): 
    # takes all the items in array2 and appends them to array1 
    itr = 0 
    array = array1 
    while itr < len(array2): 
     array.append(array2[itr]) 
     itr += 1 
    return array 



def quickSort(array): 
    lss = CounterList() 
    eql = CounterList() 
    mre = CounterList() 

    if len(array) <= 1: 
     return array # Base case. 

    else: 
     pivot = array[len(array)-1].count # Pivoting on the last item. 
     itr = 0 
     while itr < len(array)-1: 
     # Essentially editing "for i in array:" to handle CounterLists 
      if array[itr].count < pivot: 
       lss.append(array[itr]) 
      elif array[itr].count > pivot: 
       mre.append(array[itr]) 
      else: 
       eql.append(array[itr]) 
      itr += 1 

     # Recursive step and combining seperate lists.  
     lss = quickSort(lss) 
     eql = quickSort(eql) 
     mre = quickSort(mre) 
     fnl = bulk_append(lss, eql) 
     fnl = bulk_append(fnl, mre) 
     return fnl 

---

Я знаю, что это, вероятно, довольно проста, но я просто не могу показаться, чтобы увидеть проблему. (Поворотная на последнем пункте)

Вот тест им с помощью:

a = CounterList() 
a.append(CounterNode("ack", 11)) 
a.append(CounterNode("Boo", 12)) 
a.append(CounterNode("Cah", 9)) 
a.append(CounterNode("Doh", 7)) 
a.append(CounterNode("Eek", 5)) 
a.append(CounterNode("Fuu", 3)) 
a.append(CounterNode("qck", 1)) 
a.append(CounterNode("roo", 2)) 
a.append(CounterNode("sah", 4)) 
a.append(CounterNode("toh", 6)) 
a.append(CounterNode("yek", 8)) 
a.append(CounterNode("vuu", 10)) 
x = quickSort(a) 
print("\nFinal List: \n", x) 

И в результате CounterList:

['qck': 1, 'Fuu': 3, 'Eek': 5, 'Doh': 7, 'Cah': 9, 'ack': 11] 

Что вы можете сказать, отсутствует несколько значений? В любом случае спасибо за любые советы и ваше время.

Answer 1

Есть две ошибки в коде:

1. Вам не нужно «(EqL) EQL = QuickSort» линию, поскольку она содержит все одинаковые значения, поэтому нет необходимости сортировки.

2. В каждом рекурсивном вызове вы теряете опорный стержень (причина отсутствия записей), поскольку вы не добавляете его в какой-либо список. Вам нужно добавить его в eql. Таким образом, после строки коды показаны ниже:

   поворота = массив [Len (массив) -1] .count

вставить эту строку:

eql.append(array[len(array)-1]) 

удалить также ниже линию от вашего как это может иногда приводить к глубине рекурсии (только с массивами с некоторыми повторяющимися значениями, если любое повторяющееся значение выбрано как ось поворота):

eql = quickSort(eql)