Deux piles, un objectif : Comprendre l'algorithme Push Swap
Le projet Push Swap est une approche unique et stimulante du tri qui fait partie du programme de 42 School. Le but du projet est de trier un tableau d'entiers en utilisant seulement un ensemble très limité de commandes. Vous pouvez trouver le code et une explication sur la façon d'utiliser le programme dans mon référentiel GitHub .
Commençons par un peu de contexte : l'algorithme est composé de deux piles, nommées a et b . La pile a contient initialement un nombre aléatoire d'entiers positifs ou négatifs sans aucun doublon, et la pile b est vide. Le but est de trier les nombres de la pile a par ordre croissant.
Voici les commandes disponibles auxquelles le programme est limité pour trier les nombres :
Command | Description
---------|---------------------------------------------------------------
pa | push the first element of stack b to the top of stack a.
pb | push the first element of stack a to the top of stack b.
sa | swap the first two elements of the stack a.
sb | swap the first two elements of the stack b.
ss | swap a and b
ra | rotate the stack a, move the first element to the bottom.
rb | rotate the stack b, move the first element to the bottom.
rr | rotate both stacks
rra | reverse rotate the stack a, move the last element to the top.
rrb | reverse rotate the stack b, move the last element to the top.
rrr | reverse rotate both stacks
Eh bien, maintenant que nous savons cela, examinons les étapes que j'ai utilisées pour trier avec succès un tableau à l'aide de l' algorithme Push Swap . Gardez à l'esprit qu'il s'agit de mon approche personnelle et qu'il peut y avoir des millions d'autres façons d'accomplir cette tâche.
Première partie
Étape 1 : Validation des entrées
Avant de plonger dans le tri des nombres, j'effectue d'abord une vérification pour m'assurer que l'entrée est valide. Cela inclut la vérification que l'entrée est composée uniquement de nombres, qu'il n'y a pas de valeurs répétitives et que les nombres se situent dans la plage de INT_MIN et INT_MAX .
Étape 2 : Initialiser la pile A et remplir les valeurs
Après avoir validé l'entrée, l'algorithme initialise la pile a et la remplit avec les valeurs. Pour optimiser le processus de tri, j'utilise des listes chaînées, où chaque nœud inclut la valeur, l'index et un pointeur vers le nœud suivant.
Une caractéristique de cet algorithme est l'utilisation d'une fonction pour mapper et convertir les valeurs d'entrée en nombres consécutifs. Cela améliore les performances de l'algorithme lorsque les valeurs d'entrée ne sont pas déjà dans un ordre consécutif.
Étape 3 : Vérifiez les entrées triées
Une fois la pile a remplie, l'algorithme vérifie si elle est déjà triée. Si c'est le cas, le programme se termine car aucun autre tri n'est nécessaire.
Étape 4
Si la longueur de la pile a est de 3, l'algorithme appelle une fonction distincte, sort_three , pour gérer ces petites entrées. Sinon, tous les autres cas sont envoyés à la fonction de tri principale
Tri des entrées volumineuses
Maintenant, les choses commencent à devenir intéressantes. Pour les entrées plus importantes, j'appelle ma fonction sort_big pour gérer ces cas efficacement.
Étape 1 : Remplir la pile B
Je commence par transférer les valeurs de la pile a à la pile b . Pour ce faire, je calcule un ratio en fonction de la longueur de la liste. Par exemple, si la liste compte 100 éléments, le rapport serait de 14. Ensuite, je calcule la valeur plafond , qui sera utilisée plus tard dans le processus. Cette valeur est déterminée en prenant la plus petite valeur de la pile a et en y ajoutant (rapport * 2) .
Pour transférer efficacement les valeurs de la pile a à la pile b , j'utilise une méthode de recherche des première et dernière valeurs de la liste qui sont inférieures à la valeur plafond. Il est important de minimiser le nombre de commandes utilisées au cours de ce processus, donc je considère soigneusement le mouvement optimal à faire à chaque fois. Par exemple, si la première valeur correspondante est plus proche du début de la pile a que la dernière valeur correspondante est proche de la fin, je ferai pivoter la pile a pour amener la première valeur au sommet. D'autre part, si la dernière valeur correspondante est plus proche de la fin que la premièrela valeur correspondante est proche du début, je vais inverser la rotation de la pile a pour amener la dernière valeur au sommet.
Je répète ce processus de recherche du mouvement optimal et de transfert des valeurs vers la pile b jusqu'à ce que la pile a ne contienne que les trois plus grandes valeurs.
Dans l'animation ci-dessus, vous pouvez voir comment fonctionne l'algorithme. L'algorithme définit sa valeur plus élevée chaque fois qu'il ne trouve aucune correspondance en dessous dans la pile a (en incrémentant la valeur plafond de deux fois le ratio ). La raison de cette optimisation est de réduire le nombre de rotations nécessaires. Au lieu de rechercher deux morceaux distincts dans la pile a , l'algorithme en recherche deux à la fois, et lorsqu'ils sont transférés dans la pile b , ils sont automatiquement triés.
Par exemple, si la valeur est inférieure à ceiling - ratio , la pile est tournée et la valeur est envoyée à la fin de la pile b . C'est pourquoi la pile b prend la forme distincte de deux triangles. Le milieu de la pile b contient maintenant les plus petites valeurs, et les valeurs augmentent à mesure que vous vous déplacez vers les bords.
Étape 2 : Trier ce qui reste dans un
Cette étape est donc assez simple, j'appelle simplement ma fonction sort_three pour trier les trois plus grands nombres dans un fichier .
Étape 3 : repoussez tout !
Avec les valeurs de la pile b "pré-triées", l'étape finale consiste à les retransférer dans la pile a et à terminer le processus de tri !
Pour optimiser davantage les performances, j'utilise une technique de stockage temporaire des valeurs dans la partie inférieure de la pile a . Lorsque la valeur en haut de la pile b n'est pas la valeur suivante dans la séquence triée et est supérieure à la dernière valeur stockée en bas de la pile a , elle y est temporairement stockée.
Cela permet un placement efficace de la valeur dans sa position correcte dans la séquence triée finale. Lorsque la valeur est prête à être placée, elle est retransférée au début de la pile a .
Dans le cas où aucune de ces conditions n'est remplie, la valeur la plus élevée dans la pile b est recherchée et envoyée à la pile a . Cette approche permet de minimiser le nombre de commandes de rotation utilisées et accélère finalement l'ensemble du processus de tri.
Et c'est tout! Le tableau est maintenant trié par ordre croissant à l'aide de l' algorithme Push Swap .
En conclusion, l' algorithme Push Swap est une approche unique et stimulante du tri qui nécessite un peu de créativité et des compétences en résolution de problèmes. Ce n'est peut-être pas le moyen le plus rapide de trier un tableau, mais c'est un excellent exercice pour comprendre le fonctionnement des différents algorithmes de tri et comment optimiser leurs performances.
J'espère que cet article vous a permis de mieux comprendre l' algorithme Push Swap et comment l'implémenter dans vos propres projets.
![Qu'est-ce qu'une liste liée, de toute façon? [Partie 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)



































