Quicksort tri rapide illustré
Description
ce program est recusrsif et illustré , effectue un tri rapide sur un rableau , voir en dessu le principe du tri rapide ou quicksort
Principe du tri rapide
En tant que tri récursif, le tri rapide repose sur le principe :
? diviser,
? régner,
? combiner.
Diviser
Il faut d'abord choisir un élément dans le tableau, nommé pivot et noté ci-après p.
Une fois p choisi, il faut réorganiser le tableau de telle sorte que tous les éléments inférieurs au pivot soient placés au début du tableau, et tous les éléments supérieurs ou égaux soient placés à la fin du tableau. Ainsi, on peut découper le tableau de telle sorte que : pour tout élément x de t1 et pour tout y de t2, on ait x <= y.
Il est à noter que les deux sous-tableaux ainsi obtenus ne sont pas forcément de la même taille, en fonction du pivot qui aura été choisi.
Régner
On appelle la procédure récursivement pour t1 et pour t2.
Combiner
Puisque tous les éléments du premier sous-tableau sont inférieurs à n'importe quel élément du second, une fois chacun des sous-tableaux trié, il suffit de les accoler pour obtenir le tableau initial trié. La phase de combinaison est donc implicite.
Conclusion :
Principe du tri rapide
En tant que tri récursif, le tri rapide repose sur le principe :
? diviser,
? régner,
? combiner.
Diviser
Il faut d'abord choisir un élément dans le tableau, nommé pivot et noté ci-après p.
Une fois p choisi, il faut réorganiser le tableau de telle sorte que tous les éléments inférieurs au pivot soient placés au début du tableau, et tous les éléments supérieurs ou égaux soient placés à la fin du tableau. Ainsi, on peut découper le tableau de telle sorte que : pour tout élément x de t1 et pour tout y de t2, on ait x <= y.
Il est à noter que les deux sous-tableaux ainsi obtenus ne sont pas forcément de la même taille, en fonction du pivot qui aura été choisi.
Régner
On appelle la procédure récursivement pour t1 et pour t2.
Combiner
Puisque tous les éléments du premier sous-tableau sont inférieurs à n'importe quel élément du second, une fois chacun des sous-tableaux trié, il suffit de les accoler pour obtenir le tableau initial trié. La phase de combinaison est donc implicite.
Codes Sources
A voir également
- Quicksort tri rapide illustré
- Anagramme rapide - Forum Java
- Tri calcul ✓ - Forum Visual Basic 6
- Quicksort c - Forum C / C++ / C++.NET
- Tri radix ✓ - Forum Delphi / Pascal
- Algorithme de tri par base en c ✓ - Forum C
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.