Tri Quick-sort sans appel récursif

Voici donc un algo de quick sort en pascal, non recursif, qui permet de trier n'importe quel type de données avec la meilleur performance possible . Le quick sort étant sans contestation le tri le plus rapide dans un maximum de cas.

Signaler un problème

Marc-L

Expert éminent sénior

Le 25/06/2013 à 17:05

Bonjour et merci pour cette contribution !

Utilisant le tri QuickSort depuis le Quick Basic, Turbo Basic et autres, je l'ai par la suite utilisé en Turbo Pascal …

Mais un jour en VBA (Excel) je suis tombé sur un PC un peu juste en ressources plantant sur une erreur de dépassement de capacité de piles.
Je me suis rabattu sur un tri CombSort non récursif assez "rapide" jusqu'à un millier d'éléments à trier
(en fait c'est selon la génération du processeur), mais au delà, le tri QuickSort est forcément bien plus véloce !

J'ai donc adapté votre gestion de la variable tableau afin de se passer de la récursivité en VBA, je commence à 20 au lieu de 100
et la dimension de la variable augmente dynamiquement au cours de la procédure si nécessaire …

A noter qu'au cours de tests variant jusqu'à 100 000 éléments, je n'ai pas constaté avec un i5 en VBA
des écarts de temps vraiment significatifs entre la version standard et la non récursive, elles sont souvent équivalentes …
Mais même si les ordinateurs d'aujourd'hui sont assez puissants, c'est bon de savoir qu'on peut limiter les ressources
lors de centaines de milliers d'éléments à trier !

Il faudrait qu'un de ses quatre je me remette à Delphi et autres Pascal ! …

Poster un commentaire

Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.