Quicksort в python3. Last Pivot - python, python-3.x, quicksort

Дякуємо, що знайшли час, щоб прочитати це:) Я реалізую свою власну версію швидкого сортування в python, і я намагаюся змусити її також працювати в межах деяких обмежень попереднього шкільного завдання. Зауважте, що причини, які я "уникав використовувати IN", - це те, що це не було дозволено в проекті, над яким я працював (не впевнений, чому: 3).

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

Пастебіни:

• Мій 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]

У якому, як ви можете сказати, бракує декількох значень? У будь-якому випадку дякую за будь-яку пораду та ваш час.

Відповіді:

1 для відповіді № 1

У коді є дві помилки:

1. Вам не потрібен рядок "eql = quickSort (eql)", оскільки він містить усі рівні значення, тому не потрібно сортувати.

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

   pivot = масив [len (масив) -1] .count

вставити цей рядок:

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

Також видаліть нижній рядок із свого коду, оскільки це може спричинити глибину рекурсії іноді (лише з масивами з деякими повторюваними значеннями, якщо будь-яке повторне значення вибрано як стрижневий):

eql = quickSort(eql)

---