Trier rapide Recursion

Question

Je suis en train de tracer cet algorithme de tri rapide:

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

Mais avec un autre ensemble de nombres - [6,2,8,4,3,7,10]

Je suis bien une fois le côté gauche de l'algorithme est trié, mais je ne comprends pas la classe de récursion après cela.

Une fois que le côté gauche est terminé et start = 0 et end = 0, la ligne suivante fonctionne:

quicksort(myList, pivot+1, end) 

Lorsque j'imprime les valeurs de début et de fin de la fonction de tri rapide:

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

I ne comprends pas comment les variables start et end remplacent ces valeurs.

Quelqu'un peut-il expliquer comment et pourquoi?

Answer 1

Vous pourriez envisager une implémentation plus simple du tri rapide. Par exemple,

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] 

Cette implémentation plutôt simple est facile à expliquer. Vous partitionnez une liste en fonction d'un choix arbitraire du pivot. Dans ce cas arr[0] = 52. Vous parcourez alors la liste et si l'élément est supérieur au pivot (52), vous le placez dans la partition «haute» et, s'il est inférieur à 52, vous le placez dans la partition «basse». A ce stade, après une course à travers (avant que nous courons high = quicksort(high)), nous avons

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

Nous courons alors cette fonction de tri rapide sur les partitions « faible » et « élevé ». Par exemple, pour la partition haute, pivot = arr[0] = 56. Nous itérons à travers la partition haute, et si l'élément est inférieur au pivot (56), nous le mettons dans un nouveau groupe de partition faible qui est un sous-groupe de la partition haute. Si l'élément est supérieur à 56, nous le plaçons dans une partition haute qui est un sous-groupe de la partition haute. Vous pouvez le considérer comme commençant par une liste que l'on veut trier et bifurquer dans une partition haute et une partition basse qui ensuite se branche sur ses propres partitions hautes et basses. C'est là que la récursion entre