[R] Pivot Quicksort

Aide et conseils concernant AutoIt et ses outils.
Règles du forum
.
Répondre
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

[R] Pivot Quicksort

#1

Message par sozary »

Bonjour à tous.
Je cherche à faire un algorithme Quicksort avec donc la récursivité.
J'ai donc étudié attentivement l'article de jbnh sur le sujet.
Malheureusement, je n'aime pas trop sa manière de procéder, bien qu'elle soit optimale, elle n'est pas adapté à un débutant comme moi.
Je voudrais donc savoir quel pivot je pourrais choisir, et comment procéder simplement afin d'avoir quelque chose de compréhensible pour moi à coder :)!
Modifié en dernier par sozary le dim. 31 août 2014 13:21, modifié 1 fois.
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2284
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [..] Pivot Quicksort

#2

Message par jchd »

Ah, les algos de tri !

Voir ici un aperçu des possibilités de choix du pivot et les conséquences qui en découlent.
Qu'est-ce qui te pose problème ?

Sinon, plonges-toi dans une (grosse) référence sur le sujet (palmes, masque et bouteilles [d'air] impératifs !).
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [..] Pivot Quicksort

#3

Message par sozary »

Oula ^^! Je ne vais pas me lancer dans une lecture de la sorte :)!
Bien que ce livre soit intéressant, je pense pas pouvoir avoir le courage de copier chaque ligne du livre dans google traduction ;)!
" Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement.", cf wikipédia. Or, comment choisir ce pivot?
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2284
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [..] Pivot Quicksort

#4

Message par jchd »

En effet, je déconseille vivement à quiconque de se lancer dans la traduction de TAOCP. Déjà capter Knuth en intégralité demande des super-pouvoirs, alors le traduire... Pourtant il y a des traductions disponibles en chinois, japonais, thèque, roumain, russe, espagnol, polonais, allemand, macédonien, mais aucune en français conformément à notre dynamisme légendaire.

Relis bien cette partie où l'on t'expose brièvement les choix possibles et en pur hexagonal siouplé !

La justification mathématique de la complexité attendue en moyenne dans les différentes variantes n'est que de la combinatoire, mais leur développement formel est inutile ici. Pour ça, voir ton copain Knuth :mrgreen:
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [..] Pivot Quicksort

#5

Message par sozary »

"Une manière simple de choisir le pivot est de prendre toujours le premier élément du sous-tableau courant (ou le dernier)", cf. wikipédia...
Tout est dit :mrgreen: ! Je dois avoir un problème oculaire me permettant de lire uniquement une ligne sur deux :mrgreen: !
Merci!
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2284
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pivot Quicksort

#6

Message par jchd »

Le sous-titre de cette partie est "Pivot arbitraire" et on y fait bien ce qu'on dit qu'on fait : on effectue un choix arbitraire et on roule avec ça. Qu'est-ce qui te fait loucher là-dedans ?
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Répondre