Comment réparer l'étape Conquer de cette implémentation de quicksort itérative suivant l'exemple de Khan Academy?

Question

À des fins éducatives, j'essaie d'apprendre l'algorithme de tri rapide. Au lieu de vérifier une implémentation sur le web ou d'essayer de l'implémenter directement à partir du pseudo-code sur wikipedia, j'essaye une approche "hard".

J'ai regardé cette conférence de CS50 https://www.youtube.com/watch?v=aQiWF4E8flQ&t=305s afin de comprendre comment les nombres bougent tout en étant "triés rapidement". Ma mise en œuvre, que je vais montrer ci-dessous, fonctionne parfaitement pour l'exemple fourni sur la vidéo. L'exemple sur la vidéo d'un premier tableau non trié est la suivante:

C'est mon code en Python 3:

len_seq = int(input()) 

print("len_seq",len_seq) 

seq_in = list(map(int,(input()).split())) 

print("seq_in",seq_in) 

def my_quick_sort(seq): 

    wall_index = 0 

    pivot_corect_final_index_list = [] 

    while wall_index<len_seq: 

     pivot = seq[-1] 
     print("pivot",pivot) 

     print("wall_index",wall_index) 

     for i in range(wall_index,len_seq): 
      print ("seq[i]",seq[i]) 
      if seq[i]<pivot: 
       print("before inside swap,", seq) 
       seq[wall_index],seq[i]=seq[i],seq[wall_index] 
       print("after inside swap,", seq) 
       wall_index = wall_index + 1 
       print ("wall_index",wall_index) 

     print("before outside swap,", seq) 

     seq[wall_index],seq[-1]=seq[-1],seq[wall_index] 
     print("after outside swap,", seq) 

     pivot_corect_final_index = wall_index 
     print ("pivot correct final index",pivot_corect_final_index) 

     pivot_corect_final_index_list.append(pivot_corect_final_index) 
     print ("pivot_corect_final_index_list",pivot_corect_final_index_list) 

     wall_index = wall_index + 1 
     print ("wall_index",wall_index) 


    return seq 

print(my_quick_sort(seq_in)) 

Pour utiliser l'exemple de CS50 de harvard dans mon code que vous devez saisir ceci:

9 
6 5 1 3 8 4 7 9 2 

l'algorithme fonctionne très bien et retourne la sortie correcte:

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

Poursuivant mon étude, j'ai essayé de mettre en œuvre l'exemple de Khan Academy: https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort

La liste non triés dans ce cas est:

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6] 

Vous devez saisir ce qui suit dans mon code pour exécuter it:

10 
9 7 5 11 12 2 14 3 10 6 

Différemment de l'exemple de Harvard, dans ce cas mon implémentation ne fonctionne pas parfaitement. Il retourne:

[5, 2, 3, 6, 7, 9, 10, 11, 12, 14] 

Comme vous le voyez, tous les nombres que j'ai traités comme des pivots se terminent dans la bonne position. Cependant, certains nombres derrière les pivots ne sont pas corrects.

En lisant l'article de khan academy, il semble que ma mise en œuvre soit correcte lors de l'étape de partition . Cependant, il n'est pas juste sur l'étape de conquête. J'essaie d'éviter de chercher une solution finale. J'essaie d'améliorer ce que j'ai construit jusqu'ici. Je ne sais pas si c'est la meilleure méthode, mais c'est ce que j'essaie en ce moment.

Comment puis-je corriger l'étape de conquête? Est-il nécessaire d'introduire une approche récursive? Comment puis-je faire à l'intérieur mon processus itératif se passe-t-il? Et cette étape devrait-elle être introduite après avoir traité avec succès chaque pivot?

Merci pour la patience de lire ce long post.

Answer 1

Impossible de commenter, pas assez de réputation.

Lors du premier passage de votre algorithme, vous placez correctement tous les éléments plus petits que le pivot situé à gauche du pivot. Cependant, puisque votre valeur de wall_index augmente (par exemple de 0 à 1), vous ignorez l'élément le plus à gauche avec l'index 0 (il peut ne pas être dans la bonne position, il ne doit donc pas être ignoré).Dans le cas de test de l'académie Khan, le nombre 5 est placé à l'index le plus à gauche dans la première passe, puis est ignoré par les passes suivantes, il est donc bloqué sur la gauche. De même, en essayant cette modification de l'exemple harvard

9 
6 5 1 3 8 4 7 2 9 

donne

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

Après la première partition, vous devez vous assurer d'appliquer quicksort aux deux tableaux à gauche et à droite de la pivot. Par exemple, après le premier pivot (6) est placé dans la bonne position pour l'exemple Khan (ce que vous étiquetée comme l'échange extérieur),

[5, 2, 3, 6, 12, 7, 14, 9, 10, 11] 
<--1--> p <--------2---------> 

vous devez appliquer la même quicksort aux deux sous-tableaux 1 et 2 dans le diagramme ci-dessus. Je vous suggère d'essayer d'abord l'implémentation récursive, qui vous donnera une bonne idée de l'algorithme, puis essayez de l'implémenter de manière itérative.