description du programme :
il faut trier une liste d'entiers, en utilisant uniquement deux piles (a et b) et 3 actions (swap, push, rotate) et leur derivées (11 actions au total)
la methode que j'ai utilisee s'inspire du tris quicksort, qui consiste a utiliser une valeur pivot et a envoyer sur une autre pile toutes les valeurs plus petites (ou plus grandes au choix), donc on se retrouve a la fin d'un tour avec deux piles qui ne sont pas triées mais avec dans l'une tous les nombres plus petits que le pivot, et dans l'autre tous ceux plus grands
et on repete l'operation jusqu'à ce que la liste soit triee
ici, comme on n'a que deux piles disponibles, la premiere operation sera simple, mais pour les operations suivantes il va falloir trouver un moyen de distinguer des sous-listes dans chaque piles
voici le deroulement :
pistes d'ameliorations :
ressources :
- testeur : https://github.com/lmalki-h/push_swap_tester
- https://medium.com/nerd-for-tech/push-swap-tutorial-fa746e6aba1e
- https://medium.com/@jamierobertdawson/push-swap-the-least-amount-of-moves-with-two-stacks-d1e76a71789a
- ligne de commande pour generer une liste de nombres melangee :
shuf -i MIN-MAX -n SIZE))avec MIN et MAX a remplacer par la valeure maximum et SIZE par la taille de la liste
comparaison des algorithmes de tris :
source des comparaisons ci-dessous : https://www.youtube.com/watch?v=xoR-1KwQh2k
numbers comparisons array-access name
200 19 900 18 448 Bubble Sort
200 20 000 20 384 Cocktail Shaker Sort
200 19 501 19 306 Gnome Sort
200 9 568 18 752 Optimized Gnome Sort
2000 18 308 18 498 Odd-Even Sort
2000 1 999 000 3 998 Selection Sort
2000 2 002 000 4 000 Double Selection Sort
2000 965 671 19 273 364 Insertion Sort
2000 19 201 1 890 122 Binary Insertion Sort
2000 53 378 20 574 Comb Sort
2000 31 948 32 789 Shell Sort
2000 19 423 43 904 Merge Sort
2000 31 048 59 938 Binary Merge
2000 100 955 2 156 938 Weave Merge Sort
2000 19 496 43 039 TimSort
2000 1 993 119 1 930 836 Merge Sort In-Place
2000 31 022 111 758 WikiSort (Block Merge Sort)
2000 22 193 85 044 GrailSort (Block Merge Sort)
2000 30 905 10 510 Quick Sort
2000 26 160 27 488 Stable Quick Sort
2000 24 482 18 852 Dual Pivot Quick Sort
2000 37 841 40 490 Max Heap Sort
2000 37 714 42 206 Min Heap Sort
2000 21 021 26 756 Weak Heap Sort
2000 24 996 27 926 Ternary Heap Sort
2000 50 078 27 803 Smooth Sort
2000 19 410 2 000 Tournament Sort
2000 5 935 671 3 996 Cycle Sort
2000 25 711 16 616 std::sort (Introsort)
2048 33 352 25 109 Quick Shell Sort (Introsort with Shellsort)
2048 19 821 31 652 std::stable sort (Insert/Bottom-up Merge)
2000 58 367 66 296 Batcher's Odd-Even Mergesort
2000 64 832 66 118 Batcher's Bitonic Sort
200 20 099 30 684 Pancake Sort
2000 54 989 2 000 Patience Sort
2000 0 3 973 224 Gravity Sort
2000 0 6 000 Counting Sort
2000 0 4 000 Pigeonhole Sort
2000 0 12 000 Radix LSD Sort (Base 4)
2000 0 4 220 American Flag Sort (128 Buckets)
2048 0 19 207 376 Radix LSD In-Place Sort (Base 10)
2000 0 34 562 144 Radix LSD In-Place Sort (Base 2)
2000 0 26 000 Radix MSD Sort (Base 4)
2000 0 46 000 Radix MSD Sort (Base 2)
2000 0 80 048 Shatter Sort
2000 0 12 000 Simple Shatter Sort
2000 5 044 6 098 Flash Sort
2000 28 868 55 742 Time Sort (Mul 4) + Insertion Sort
200 797 161 19 928 Stooge Sort
200 50 783 400 Bad Sort
200 114 006 565 19 276 Silly Sort
200 114 006 565 20 716 Slow Sort
200 100 437 4 771 028 Less Bogo Sort
200 131 994 2 472 298 Cocktail Bogo Sort
10 4 875 249 56 784 400 Bogo Sort
autre source de comparaison : https://www.toptal.com/developers/sorting-algorithms push_swap_visalizer : https://github.com/o-reo/push_swap_visualizer