begin process at 2012 05 27 18:01:13
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Graphique

 > QUICKSORT TRI RAPIDE ILLUSTRÉ

QUICKSORT TRI RAPIDE ILLUSTRÉ


 Information sur la source

Note :
7 / 10 - par 1 personne
7,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Graphique Classé sous :trirapide, quicksort, illustré, recursif, yms Niveau :Initié Date de création :28/02/2006 Date de mise à jour :28/02/2006 17:51:48 Vu / téléchargé :12 291 / 804
Auteur : yms

Ecrire un message privé
Site perso
Commentaire sur cette source (8)
Ajouter un commentaire et/ou une note

 Description

ce program est recusrsif et illustré , effectue un tri rapide sur un rableau , voir en dessu le principe du tri rapide ou quicksort


 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.

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

28 février 2006 17:39:13 :
correction de l'orthographe
28 février 2006 17:51:49 :
correction orthographe

 Sources du même auteur

Source avec Zip LES HUIT REINES
Source avec Zip LABYRINTHE ILLUSTRÉ
Toutes les sources de yms

 Sources de la même categorie

Source avec Zip Source avec une capture PLANNING D'EQUIPE par grephit
Source avec Zip APPLICATION DE DESSIN DE QUELQUES FIGURES par laguchori
Source avec Zip Source avec une capture HDR EXPOSURE FUSION par mecrosoft
Source avec Zip Source avec une capture IRC CLIENT MULTISERVEUR EN MFC (TXIRC) par TeniX
Source avec Zip ENTETE DU FICHIER BMP (BIPMAP) par k.Lutchi
Toutes les sources de la catégorie Graphique

 Sources en rapport avec celle ci

Source avec Zip TESTS DE TRIS (WIN32) par BruNews
Source avec Zip COMBSORT ALGORITHME DE TRI SIMPLE RAPIDE NON-RECURSIF par xtremejames183
Source avec Zip TABLES DE TRI ASSOCIES AUX FICHIERS par Stanel
Source avec Zip LE QUICKSORT NON-RECURSIF ET L'IMPACT DE L'INSERTIONSORT SUR... par nickydaquick
Source avec Zip LES HUIT REINES par yms

Commentaires et avis

Commentaire de BruNews le 28/02/2006 21:58:34 administrateur CS

Le principe du tri RAPIDE serait plutot de supprimer la récursivité.

Commentaire de nickydaquick le 01/03/2006 12:29:36

Salut, Bonne Initiative quant a deposer un algorithme aussi utilise que le Tri rapide . Mais comme le dit BruNews un peu avant , pour ameliore ton algorithme il te faudrait utiliser une boucle ( do .. while) avec une file par exemple ... tu supprimerais les delais du aux appels de fonctions( push et pop en tout genre), et les surcharges de la pile. Je voudrais aussi noter que ton tri rapide n'est vraiment efficace que pour des tailles raisonnables( ni trop petites => tri par insertion  , ni trop grosses => tri sur le tas) et donnees primitives ( pas pour de gros objets auquel cas tu utiliseras un tri indirect)

Commentaire de ncoder le 01/03/2006 18:25:07

"les huits renes est un program illustrer recursive"

Commentaire de : yms le 28/02/2006 17:33:47  je le ferai pas en future, mais pour votre remarque bien je ne suis pas francais de langue, donc j'essaie de mon mieu


Dans l'explication finale, il est pas mal ton français par rapport à celui là...

;)

Commentaire de yms le 01/03/2006 21:11:09

merci pour la remarque sur mon francais , mais quand j'ai lu la remarque la premiere fois, je me suis dis c'est vraie je dois faire attention et c'est ce que j'ai fais tout de suite apres , mais je dois dire vous avez une bonne observation...
la recursivité, je l'ai fais parceque quand j'ai lu le principe j'ai trouvé que la recursivité est necessaire, mais je tiendrai en compte votre remarque et je chercherai une autre solution. merci

Commentaire de vecchio56 le 01/03/2006 23:01:22 administrateur CS

En tant que tri récursif, le tri rapide repose sur le principe :
• diviser,
• régner,
• combiner.

J'adore l'explication. Tu peux préciser ce que tu entends pas régner? Je connais l'expression "diviser pour régneré", mais j'ignorais que régner était une étape précise du tri...

Concernant la remarque de BruNews sur la récursivité, je suis pas vraiment d'accord. Le tri rapide est un algo récursif (c'est toujours comme ca qu'on le présente). J'ose pas imaginer la tête de cet algo en non récursif

Commentaire de yms le 01/03/2006 23:09:23

l'explication du principe je l'ai pris de l'enoncé que j'ai eu pour la realisation de ce programme, je ne vois pas aussi l'interet mais je voulais pas l'enlever pour me garder neutre de l'enoncé . "diviser pour regné" c'est pour la methode merise et ca n'a rien a voir , je le reconnais!

Commentaire de vecchio56 le 01/03/2006 23:12:52 administrateur CS

Si si c'est bien diviser pour régner qui est utilisé ici. Seulement je trouve ca marrant de dire que diviser pour régner c'est
1) diviser
2) régner

Commentaire de BruNews le 02/03/2006 01:32:02 administrateur CS

Je suis sur que tu as déjà vu, ici:
http://www.cppfrance.com/code.aspx?id=11151

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

parcours (recursif) d'un repertoire + listage [ par goth ] sachant que je vais me servir de vc++ 6 j'aimerais savoir comment parcourir un repertoire(recursivement) et ses entrées puisque, a priori(sauf erreur tri rapide (quicksort) et/ou tri par tas(heapsort) urgent [ par mersniyassine ] je trouve une difficulté a simuler graphiquement en C ces 2 trisya t-il quelqu'un qui peut me fournir un code.c compilable sur Turbo C qui effectue u quicksort ! [ par Shadow95 ] Est-ce que qqun sait coder un quicksort en C ? Je bute là dessus depuis pas mal de temps et kan je vois que vous coder tous le quicksort en C++ . . . Trier un fichier.txt, avec des pointeurs par QuickSort [ par miss_aurel_8 ] Bonjour, je suis débuttante en C++ et j'ai besoin d'aide pour une fonction de tri.Voila mon pb :j'ai un fichier .txt tout simple avec des numéro de cl QuickSort : liste chaînée [ par vegeta07 ] Salut, Je souhaite r&#233;aliser le tri QuickSort (r&#233;cursif) sur une liste simplement cha&#238;n&#233;e. Mais j'ai un probleme sur la recursivit Quicksort, condition d'arrêt le probleme ? [ par italiasky ] Bonsoir,  En cette période de fêtes, je viens à la recherche d'une bonne âme. lol Non bon alors un peu de sérieux, j'ai un projet d'info sur Quicksort sans récurisivité ( appel a sa propre fonction) en pur C [ par xtremejames183 ] Voila le topo , sachant que la récursivité est un  gouffre de mémoire sinon une m**** ,je cherche une fonction de tri rapide(QSort) en pur C sans avoi spline cubique mais en recursif ? [ par vgaudin ] Bonjour tous, Je souhaiterais savoir si il existe des algos permettant de calculer l'integrale d'une spline cubique mais en recursif. J'ai déjà mon language c ][principe recursif [ par marie0marie ] bonjour , je besoin de programme qui multiplie les deux entiers positifs a et b selon le principe récursif suivant: A*b=a*(b-1)+a si b est impaire A*


Nos sponsors


Sondage...

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,484 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)