Quicksort und Rekursion in Python

Question

Ich versuche Quicksort in Python mit 2 Hauptfunktionen zu implementieren - Partition und Quicksort. Die Partitionsfunktion ist so konzipiert, dass sie 2 Arrays zurückgibt - größer und kleiner als p. danach wird Quicksort auf beiden separat aufgerufen. so funktioniert die quicksort wie folgt aus:

def quicksort(array) 
    pivot = 0 # pivot choice is irrelevant 
    left,right = partition(array,pivot) 
    quicksort(left) 
    quicksoft(right) 
    return left+right 

Aber aus meinem Verständnis sollte es möglich sein Partition zu entwerfen nur einen einzigen Index zurückzukehren - abgrenzt größere und kleinere Arrays und Redesign quicksort wie folgt:

def quicksort(array) 
    pivot = 0 # pivot choice is irrelevant 
    i = partition(array,pivot) 
    quicksort(array[:i-1]) 
    quicksoft(array[i:]) 
    return array 

aber diese Implementierung kehrt teilweise sortierten Array

original array [5, 4, 2, 1, 6, 7, 3, 8, 9] 
sorted array [3, 4, 2, 1, 5, 7, 6, 8, 9] 

was ich hier fehlt?

Answer 1

, ohne den Code zu sehen, es ist schwer, sicher zu sein, aber ein möglicher Fehler ist die i-1:

>>> [1,2,3,4][:2] 
[1, 2] 
>>> [1,2,3,4][2:] 
[3, 4] 

(?, Obwohl Sie einfach den Dreh Skipping sein kann)

auch, sind Scheiben neue Listen , nicht Ansichten:

>>> l = [1,2,3,4] 
>>> l[2:][0] = 'three' 
>>> l 
[1, 2, 3, 4] 

, die unglücklich ist (das typische Funktionsprogramm quicksort tun, die überhaupt keinen quicksort ist, verdammt noch mal, weil es ein Pi zu schaffen le neuen Arrays ärgert mich auch ...)

Sie rund um das zweite Problem, das durch die gesamte Liste vorbei und lo/hallo Indizes arbeiten können:

def quicksort(data, lo=0, hi=None): 
    if hi is None: hi = len(data) 
    .... 

Answer 2

quicksort(array[:i-1]) nicht wirklich nennt quicksort auf dem ersten Partition des Arrays, es ruft Quicksort auf eine Kopie der ersten Partition des Arrays. Daher partitioniert der Code das Array an Ort und Stelle, erstellt dann Kopien der Hälften und versucht, sie zu sortieren (aber niemals etwas mit den resultierenden Arrays zu tun), so dass Ihre rekursiven Aufrufe keine Wirkung haben.

Wenn Sie es so machen wollen, müssen Sie vermeiden, Kopien der Liste mit Slicing zu erstellen und stattdessen die gesamte Liste sowie die Bereiche, auf die Ihre Funktionen angewendet werden sollen, zu übergeben.

Answer 3

Ich hatte das gleiche Problem, mein Quicksort gab teilweise sortierte Listen zurück. Ich fand das Problem war, dass ich den Pivot in seinem eigenen Array nicht zurückgab. Wenn ich ein Array für den Pivot erzeuge, kann die Rekursion korrekt funktionieren.

dh. meine Partitionsfunktion zurückgibt statt:

Rückkehr nach links, rechts

kehrt

Rückkehr links, pivotval, rechts