Quicksort Rekursion

Question

Ich versuche, diesen schnellen Sortieralgorithmus zu verfolgen:

https://pythonschool.net/data-structures-algorithms/quicksort/

Aber mit einem anderen Satz von Zahlen - [6,2,8,4,3,7,10]

Mir geht es gut, wenn die linke Seite des Algorithmus ist sortiert, aber ich verstehe die Rekursionsklasse danach nicht.

Sobald die linke Seite abgeschlossen ist und start = 0 und end = 0, die folgende Zeile läuft:

quicksort(myList, pivot+1, end) 

Wenn ich die Anfangs- und Endwerte von der schnellen Sortierfunktion ausdrucken:

Start = 2 and End = 1 
Start = 3 and End = 2 
Start = 4 and End = 6 

I verstehe nicht, wie sich die start und end auf diese Werte ändern.

Kann jemand erklären, wie und warum?

Answer 1

Sie könnten eine einfachere Implementierung von Quicksort in Betracht ziehen. Zum Beispiel

my_list = [52,8,45,43,6,56,76,36,54,12,34,98,41,30] 

def quicksort(arr): 
    high = [] 
    low = [] 
    pivot_list = [] 

    if len(arr) <= 1: 
     return arr 
    else: 
     pivot = arr[0] 
     for i in arr: 
      if i < pivot: 
       low.append(i) 
      elif i > pivot: 
       high.append(i) 
      else: 
       pivot_list.append(i) 
     high = quicksort(high) 
     low = quicksort(low) 

    return low + pivot_list + high 

print quicksort(my_list) 

[6, 8, 12, 30, 34, 36, 41, 43, 45, 52, 54, 56, 76, 98] 

Diese recht einfache Implementierung ist leicht zu erklären. Sie partitionieren eine Liste basierend auf einer beliebigen Wahl des Pivots. In diesem Fall arr[0] = 52. Sie durchlaufen dann die Liste und wenn das Element größer ist als der Pivot (52), legen Sie es in die 'high' Partition und wenn es kleiner als 52 ist, legen Sie es in die 'low' Partition. An diesem Punkt nach einem Durchlauf (bevor wir high = quicksort(high) laufen), haben wir

low = [8, 45, 43, 6, 36, 12, 34, 41, 30] 
high = [56, 76, 54, 98] 
pivot_list = [52] 

Wir haben dann diese quicksort Funktion laufen auf den ‚low‘ und ‚hoch‘ Partitionen. Zum Beispiel für die hohe Partition pivot = arr[0] = 56. Wir durchlaufen die hohe Partition und wenn das Element kleiner ist als der Pivot (56), setzen wir es in eine neue niedrige Partitionsgruppe, die eine Untergruppe der hohen Partition ist. Wenn das Element größer als 56 ist, setzen wir es in eine neue hohe Partition, die eine Untergruppe der hohen Partition ist. Sie können sich vorstellen, dass wir mit einer Liste beginnen, die wir sortieren und in eine High-Partition und eine Low-Partition verzweigen möchten, die dann jeweils in ihre eigenen High- und Low-Partitionen verzweigen. Hier kommt die Rekursion in