dont ask to ask
Groupe : Anciens
|
Un qsort simpe sur des listes, en OCaml :
Code : OCaml1
2
3
4
5 | let rec qsort liste = match liste with
[] | _::[] -> liste
| pivot::reste ->
let debut, fin = List.partition (fun a -> a < pivot) reste in
qsort debut @ [pivot] @ qsort fin
|
Version générique :
Code : OCaml1
2
3
4
5
6
7 | let qsort ( < ) liste =
let rec sort li = match li with
[] | _::[] -> li
| pivot::reste ->
let debut, fin = List.partition (fun a -> a < pivot) reste in
sort debut @ [pivot] @ sort fin
in sort liste
|
|
Aimez-vous le C++ ?
Ville : Durham
Pays : Royaume-Uni
Études : EPFL
|
Hello, bon tuto, clair et précis.
Cependant j'aurais ajouté le fait que la fonction sort de la librairie <algorithm> de la STL le fait (pou ceux qui codent en C++), vu que tu l'as mis pour le C.
|
la vie est un programme
Ville : Casablanca
Pays : Maroc
Études : SUPINFO Maroc à Casablanca
|
tres bon le tuto .
17/20 , pasque j'aurait prefere que le code soit ecrit en C . 
- La répétition est humaine , la récurrence Divine .
- il faut être fou pour ne pas utiliser la récursivité quand il le faut !
|
"Se coucher tard nuit"
|
hm... après presque 8000 visualisations j'ai des doutes mais, l'implémentation C ne serait-t-elle pas buguée ?
Secret (cliquez pour afficher)Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 | #include <stdio.h>
void permuter(int tab[], int i, int j)
{
int temp = tab[i];
tab[i] = tab[j];
tab[j] = temp;
}
void quickSort(int tab[], int debut, int fin)
{
int gauche = debut;
int droite = fin;
const int pivot = tab[debut];
if(debut >= fin)
return ;
while(1)
{
for( ; tab[gauche] < pivot; gauche++) {}
for( ; tab[droite] >= pivot; droite--) {}
if(gauche < droite)
{
permuter(tab, gauche, droite);
}
else
{
break;
}
}
quickSort(tab, debut, gauche-1);
quickSort(tab, gauche+1, fin);
}
void aff(int t[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",t[i]);
printf("\n");
}
int main(void)
{
int tab[] = {5,2,9,4};
aff(tab,4);
quickSort(tab,0,3);
aff(tab,4);
return 0;
}
|
Code : Console | $ gcc qsort.c
$ ./a.out
5 2 9 4
2 4 9 5 |
En passant, on voit deux licences contradictoire je crois.
...clap clap!  
|
Ville : St nicolas de macherin
Pays : France métropolitaine
|
Juste une remarque sur le code en C, pourquoi écrire un "while(1)" qui contient un break conditionnel ? Les parenthèses sont là pour exprimer une condition de sortie. Si ton but est de t'assurer que la boucle soit parcourue au moins une fois, do...while est là pour ça.
Ca ne compromet pas l'interêt de ton tuto, mais sur un site parcouru par beaucoup de débutants, autant ne pas trop écrire de "bizarreries" dans les codes fournis.
|
Chieur professionnel
|
Citation
Lors des appels récursifs, trier d'abord le sous-tableau le plus long et ensuite le sous-tableau le moins long. C'est juste un test de plus, et ça peut accélerer le tri (ne me demandez pas pourquoi...)
Récursion terminale probablement (faire ça garantit une pile de taille O(ln(N)) dans tous les cas).
Citation
Mélanger le tableau aléatoirement avant de le trier. Ça paraît débile, mais QSort adore les tableaux bien mélangés et a horreur de ceux déjà presque triés. En utilisant un mélange avant QSort, on augmente les chances d'avoir une liste très désordonnée.
Il est plus simple de prendre un pivot au hasard.
Freecircus : il faut effectivement trier récursivement de debut à gauche-1 et de gauche à fin.
Les caisses sont vides
Traité européen de 1965 :
Citation : Traité
FONCTIONNAIRES ET AGENTS DES COMMUNAUTÉS EUROPÉENNES
Article 12
Sur le territoire de chacun des États membres et quelle que soit leur nationalité, les fonctionnaires et autres agents des Communautés:
a) jouissent de l'immunité de juridiction pour les actes accomplis par eux, y compris leurs paroles et écrits, en leur qualité officielle, sous réserve de l'application des dispositions des traités relatives, d'une part, aux règles de la responsabilité des fonctionnaires et agents envers les Communautés et, d'autre part, à la compétence de la Cour pour statuer sur les litiges entre les Communautés et leurs fonctionnaires et autres agents. Ils continueront à bénéficier de cette immunité après la cessation de leurs fonctions,
|
Attention, je mords !
|
Freecircus/Pole : Corrigé en local, merci. Effectivement, c'est resté longtemps inapperçu. Vu que mon tuto est déjà apparu dans la box de la page d'acceuil récemment, j'hésite à le « upper » encore une fois pour une seule ligne, cependant...
Pole : Je pense que c'est du tail-rec ausi, mais j'ai de fortes chances de dire n'importe quoi si j'explique ça. Et pour prendre un pivot au hasard, est-ce que ça règle le problème aussi bien ?
Panpan, il est vrai que c'est une bizarrerie, mais, quand j'ai rédigé le tuto, cette version m'a paru plus « sémantique » : on fait ceci et celà, puis si on a pas fini, on permute, sinon, on sort de la boucle (je voulais faire apparaître le : sinon, on seort de la boucle).
|
|
Citation : GuilOooo Freecircus/Pole : Corrigé en local, merci.
Vérifies bien ta correction. Je préconise de tester sur au moins trois types de tableaux (de grande taille, de préférence) :
- un tableau trié a l'endroit
- un tableau trié a l'envers.
- un tableau aléatoire avec doublons.
Citation : GuilOoooEt pour prendre un pivot au hasard, est-ce que ça règle le problème aussi bien ?
Logiquement, cela devrait.
Citation : WikipédiaLe problème le plus important est le choix du pivot. Une implémentation du tri rapide qui ne choisit pas adéquatement le pivot sera très inefficace pour certaines entrées. Par exemple, si le pivot est toujours le plus petit élément de la liste, QuickSort sera aussi efficace qu'un tri par sélection, c'est-à-dire de performance O(n²).
[...]
Des données triées ou partiellement triées sont relativement fréquentes dans la pratique et l'implémentation naïve du tri rapide qui choisit le premier élément comme pivot conduit à une profondeur de récursivité linéaire. Pour résoudre ce problème, on peut utiliser l'élément du milieu du tableau. Cette façon de faire fonctionne bien pour les listes déjà triées ou à l'envers mais facilite la mise au point d'attaques.
Citation : GuilOooo - tutoLors des appels récursifs, trier d'abord le sous-tableau le plus long et ensuite le sous-tableau le moins long. C'est juste un test de plus, et ça peut accélerer le tri (ne me demandez pas pourquoi...)
Que veux tu dire ? Wikipédia est bien plus clair, je trouve :
Citation : WikipédiaUne autre solution simple pour réduire l'utilisation de la mémoire par un tri rapide utilise une récursion pour la plus petite des sous-listes à trier, et une récursion finale (qui peut donc être transformée en une boucle) pour la plus grande. Ceci limite la quantité de mémoire utilisée a O(log n).
Voici un qsort générique que j'ai écrit en C, mettant en application les deux optimisations dont tu parle. Les améliorations ont vraiment été très sensibles a l'exécution :
- Avant amélioration de la récursivité, la pile sautait assez rapidement (surtout sur des tableaux tries).
- Avant amélioration de choix du pivot, les tris sur listes déjà triées n'étaient pas du tout rapides (moins rapides qu'un isort)... A noter aussi que cela suffit a améliorer la gestion mémoire dans la plupart des cas.
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | #define swap(p1,p2,sz) { \
size_t j; \
for (j=0; j<sz; j++) \
{ \
char ptmp = *(p1+j); \
*(p1+j) = *(p2+j); \
*(p2+j) = ptmp; \
} \
}
void my_qsort
(void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))
{
char *debut, *fin, *gauche, *droite, *pivot;
debut = base;
fin = debut+(size*nmemb)-size;
while (debut < fin)
{
gauche = debut;
droite = fin;
/* on choisit un pivot au milieu du tableau,
(et on le place au début pour le partitionnement) */
swap (debut, debut+(((fin-debut)/(size*2))*size), size);
pivot = debut;
/* Partitionnement */
do
{
while (gauche < droite && compar(droite, pivot) > 0)
droite -= size;
swap (gauche, droite, size);
pivot = droite;
while (gauche < droite && compar(gauche, pivot) <= 0)
gauche += size;
swap (droite, gauche, size);
pivot = gauche;
}
while (gauche < droite);
/* Pour minimiser les appels récursifs */
if (gauche-debut < fin-gauche)
{
my_qsort(debut, (gauche-debut)/size, size, compar);
debut = gauche+size;
}
else
{
my_qsort(gauche+size, (fin-gauche)/size, size, compar);
fin = gauche-size;
}
}
}
|
|
|
|
Merci pour ce tut,très clair et bien écrit.
Néanmoins j'aurai une petite question;
Lors d'un appel une fois la boucle While terminée,ne faudrait il pas placer le pivot à sa bonne place?! (juste avant de faire l'appel de la procédure avec les deux sous-tableaux)
|
|
|
std::sort (partial_stable_sort & cie) ne sont pas des quick-sort. Leur complexité ne dégénère pas en O(N²) dans le pire des cas. Cf une vraie doc -> http://www.sgi.com/tech/stl/sort.html
|
|
|
Bonjour,
Je viens de lire en entier le tuto ainsi que vos commentaires et j'aimerai precise certains points.
L'auteur de ce tuto dit : Citation : GuilOoooMélanger le tableau aléatoirement avant de le trier. Ça paraît débile, [...] en effet c'est totalement debile.
Le tri rapide essaye d'etre aussi fidele a son nom "tri rapide", melanger le tableau est une operation en O(n) qu'il faudra rajoute a la complexite totale de l'algorithme.
Citation : GuilOoootrier d'abord le sous-tableau le plus long et ensuite le sous-tableau le moins long.
Non c'est l'inverse en effet imaginons qu'apres la fonction de partionnement on est un tableau "divise" en 1/4 - 3/4. log(n/4) < log(3n/4), CQFD.
Citation : GuilOoooUtiliser un autre algorithme de tri sur les sous-tableaux quand ils deviennent trop petits.
En effet et il serai meme bon d'indique lequel. (tri selection)
Citation : GuilOoooChoisir un bon pivot
Indique comment, par exemple en utilisant la mediane des trois (debut - milieu - fin) ou bien s'il y a risque d'attaque (debut - milieu - fin piege en y placent les plus petites valeurs de la collection) simplement prendre l'element median de la serie (debut - milieu - aleatoire) car un pivot aleatoire evite le cas de recursion lineaire et le temps d'execution quadratique. (bien entendu aleatoire doit etre different de debut - milieu - fin)
Enfin juste pour conclure si vous voulez limite la profondeur d'appel a O(log(n)) il convient de gerer soit meme un pile et de respecter les points que j'ai cite ci dessus, l'algorithme n'est plus coder recursif mais iteratif meme si dans le principe il fonctionne de maniere recursif.
Ciao...
|
Attention, je mords !
|
Merci pour ces commentaires pertinents, lmghs et gnairod.
Citation : gnairod
Le tri rapide essaye d'etre aussi fidele a son nom "tri rapide", melanger le tableau est une operation en O(n) qu'il faudra rajoute a la complexite totale de l'algorithme.
Du coup, il reste toujours en O(n*log(n)) en moyenne, vu qu'une constante multiplicative ne change pas la complexité globale ? Or, dans des cas où l'entrée à de fortes chances d'être ordonnée, on tombera souvent dans du O(n²). Il y a donc un gain dans ces cas là.
Citation : gnairodNon c'est l'inverse en effet imaginons qu'apres la fonction de partionnement on est un tableau "divise" en 1/4 - 3/4. log(n/4) < log(3n/4), CQFD.
C'est vrai, étourderie de ma part. Corrigé en local, ça passera lors de la prochaine validation du tutoriel (comme la remarque concernant le commentaire de lmghs).
Citation : gnairod
En effet et il serai meme bon d'indique lequel. (tri selection)
On a le choix. J'ai déjà vu des implémentations de QuickSort avec un tri par insertion pour finir le boulot. C'est ajouté en local.
Citation : gnairod
Indique comment, [...]
J'explique déjà que l'élément médian de la série est un bon choix. Vu que ce n'est qu'une « piste à explorer », je n'en parle qu'évasivement, car ce n'est pas le but du tuto. Du coup, est-ce vraiment pertinent de s'étendre là dessus ?
Bonne soirée
|
|
|
Citation : GuilOooo Du coup, il reste toujours en O(n*log(n)) en moyenne, vu qu'une constante multiplicative ne change pas la complexité globale ?
Ce n'est pas une constante multiplicative O(n)...
Et bien que l'on marque uniquement "la fonction" qui domine avec la notation de Landau il faut garde en tete que cela n'est qu'un ordre d'idee du nombre de comparaison effectuer par l'algorithme. En effet compare le tri rapide et le tri par tas. Pourquoi le tri par tas est-il en general toujours deux fois plus lent que le tri rapide? Tout simplement parcequ'il ne lit pas de maniere sequentiel les donnees en memoire mais aussi parcequ'il transforme le tableau en un tas ce qui neccessite n - 1 comparaisons donc O(n).
Citation : GuilOoooOn a le choix. J'ai déjà vu des implémentations de QuickSort avec un tri par insertion pour finir le boulot. C'est ajouté en local.
Effectivement mais un tri par insertion est rapide ssi les donnees sont presques deja trier or la fonction de partitionnement a de forte chance de ne pas rendre une sous partie presque deja trier.
Citation : GuilOoooJ'explique déjà que l'élément médian de la série est un bon choix. Vu que ce n'est qu'une « piste à explorer », je n'en parle qu'évasivement, car ce n'est pas le but du tuto. Du coup, est-ce vraiment pertinent de s'étendre là dessus ?
Bien sur que c'est important! Le tri rapide repose sur la fonction de partionnement. Plus cette derniere choisira un pivot pertinant et rapidement plus l'algorithme s'executera rapidement. Preuve : Si le choix du pivot est toujours l'element le plus faible du tableau la complexite est de O(n^2).
|
Nettoie ce qui n'est pas toi.
Études : IUT Aix-en-Provence
|
Bon tuto .
|
Ville : Brest
Pays : France métropolitaine
|
Sympa tu aurais pu parler du tri fusion qui est dans la même idée de « diviser pour régner » au niveau complexité c'est aussi en O(n*log n). Sinon voilà comment je faisait pour partager la liste en deux sans List.partition
Code : OCaml 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | (* Quick Sort en caml *)
(* Principe du QS : on sépare la liste en deux sous liste suivant le pivot
on prendra ici le premier élément de la liste.
Et on fait pareil avec les sous listes *)
let rec partition pivot l1 l2 = function
| [] -> (l1,l2)
| a :: r -> let (l1,l2) = partition pivot l1 l2 r in
if (a < pivot) then ((a::l1),l2) else (l1,(a::l2))
;;
let rec qsort = function
| [] -> []
| pivot :: r -> let (l1,l2) = (partition pivot [] [] r) in
qsort l1 @ [pivot] @ qsort l2;;
|
(source : http://nax.alwaysdata.net/blog/?article15/quick-sort-ocaml)
À priori sur une liste aléatoire le pivot est plutôt bien choisi (en moyenne) mais c'est mauvais sur une liste triée.
|
dont ask to ask
Groupe : Anciens
|
Citation
La complexité de cet algorithme est plus difficile à évaluer que celle du tri à paniers, cependant. Il faut faire un peu de maths, et fournir des explications accessibles n'est pas toujours facile. Alors, de peur de vous dire une bêtise, je ne vais pas entrer ici dans le détail.
On sait que, dans la plupart des cas, nous allons avoir environ 1.38*N*log(N) opérations à réaliser pour N cases à trier. Ce qui nous donne, si on simplifie en enlevant les constantes, une complexité de O(N*log(N)). (On note O( nombre ) la complexité d'un algorithme). Cette complexité est très compétitive.
Stop the bullshit.
Ce paragraphe ne veut pas dire grand chose (complexité dans la plupart des cas ? ça ne veut rien dire, il y a la complexité dans le pire cas et la complexité dans le cas moyen). Produire une constante ici c'est juste ridicule (oui alors j'ai lu un gros calcul qui dit que ...), d'ailleurs la constante donne le nombre de comparaisons dans le cas moyen, et pas le nombre d'opérations dans le cas moyen.
Je pense qu'il faudrait respecter deux règles de bon sens sur le SdZ :
- ne jamais énoncer de résultat qu'on n'est pas capable d'expliquer à un lecteur motivé (je ne parle pas de prouver rigoureusement, mais au moins de justifier et de donner une compréhension intuitive). Sortir des constantes c'est ridicule et ça ne sert à rien, surtout quand la formulation révèle une compréhension du sujet laissant à désirer
- éviter à tout prix les résultats dont on ne maîtrise pas soi-même la preuve rigoureuse
Dans ce cadre, il faudrait toujours commencer par la complexité dans le pire cas (car elle est souvent facile à comprendre et à calculer), parler ensuite d'efficacité en pratique (parce que c'est ce qui compte en pratique) et l'expliquer éventuellement par une complexité dans le cas moyen : c'est le concept le plus difficile, donnant lieu au plus grand nombre d'erreurs, et qui n'est en général pas maîtrisé par les auteurs eux-mêmes.
Annoncer des résultats théoriques qu'on ne maîtrise pas bien, c'est courir au désastre. La complexité est une manière pour chacun d'améliorer ses pratiques et d'y apporter de la rigueur, quand elle est utilisée à bon escient. Ce ne doit pas être un argument d'autorité scientifique à asséner aux endroits où on ne comprends pas ce qui se passe. "C'est prouvé mathématiquement, O(n log n) dans la plupart des cas, tu peux pas comprendre mais fais moi confiance t'inquiète". Beurk.
Facts :
- le tri rapide n'est pas un tri optimal; sa complexité n'est pas compétitive
- le nombre de comparaison "en moyenne" (sur une entrée uniforme) du tri rapide est supérieur au nombre de comparaisons du tri fusion
- le tri rapide est en pratique un bon tri; cela vient en général de facteurs bas niveau (gestion du cache / localité), et dépend fortement de l'implémentation
- une implémentation naïve du choix du pivot pose problème en pratique : tant qu'on n'a pas un choix du pivot randomisé, on risque de se faire avoir; si le lecteur ne comprend pas pourquoi, il ne devrait pas utiliser le tri rapide
Si on veut un bon tri, il faut utiliser le tri déjà codé de la bibliothèque logicielle que l'on a à disposition. Pas besoin de convaincre le lecteur avec des arguments de marchands de tapis.
|
Toi-même.
Ville : Franière
Pays : Belgique
Études : Faculté Universitaire Notre Dame de la Paix (Namur)
|
STOOOOP ! Vous parlez de truc auquel moi je comprend quasi rien la. Je pose clairement la question : "Cet algo est-il efficace ? Plus ou moins que par exemple le tri fusion ? (un peu le même principe d'ailleurs) et que faut-il mieux choisir comme pivot,en pratique ?". C'est ça qu'un zéro moyen veux savoir, non ?
Note: bizarement, en cliquant dessus, j'ai crû a un tuto sûr une class de QT. Tu devrai renommer le titre en "QuickSort", qu'on ne confonde pas. Enfin, je croîs.
Venez aidez sur les NC !
Hardware : HP 6830s - Ubuntu 11.10
Languages de programation : C - C++ - Python
Bibliothèques (C/C++) : SDL - Qt - OpenGL - GTK+
Script : bash
Site web : PHP - SQL - HTML - CSS
|
dont ask to ask
Groupe : Anciens
|
pierre_24 > oui, l'algorithme est assez efficace quand tu fais un "bon" choix de pivot. En pratique, choisir un pivot au hasard dans le tableau est à la fois simple et assez efficace (ça te protège plutôt bien des cas pathologiques). On peut faire plus élaboré (à base de calcul de médiane) pour un gain pas forcément évident.
En pratique, cet algorithme sera un peu plus rapide qu'un tri fusion, mais c'est lié à des détails techniques du fonctionnement de l'ordinateur. Par ailleurs il faut se méfier, car les performances du tri rapide peuvent beaucoup se dégrader dans de rares cas (enfin, rares ou pas, si on choisit mal son pivot), alors qu'un tri par fusion, bien qu'un peu plus lent, aura des performances correctes dans tous les cas : si tu travaillais sur un système critique où tu ne peux pas te permettre de délai inattendu (un centrale nucléaire, ou même un ordinateur de bord embarqué dans une voiture), c'est un critère à prendre en compte.
Un autre tri assez utilisé est le tri par tas; une bonne implémentation est aussi rapide, voire plus rapide que le tri rapide, mais elle est un plus compliquée et difficile à comprendre, et dans la plupart des cas il vaut mieux faire simple et juste que compliqué et peut-être faux.
Le reste, c'est soit des détails, soit du truandage.
|
Faisons semblant
|
bluestorm : je ne vois pas en quoi s'appuyer sur des démonstrations mathématiques pose problème et même si l'on a sois-même du mal à les comprendre. C'est un peu ce que l'on fait toute sa scolarité avec le théorème de Pythagore ou encore celui de Thalès et ça marche. Ensuite oui, tu soulèves encore le problème du "plupart des cas" et qui est effectivement pertinent. Parce que pour toi, la "plupart des cas", c'est "la plupart des cas" en pratique et en pratique ce qui tombe assez souvent est une entrée triée ou presque déjà triée, entrée pour laquelle, si l'on prend le pivot au début ou à la fin de la partition comme c'est le cas dans l'implémentation de GuilOooo, un tri rapide serait quadratique. C'est effectivement un point à corriger dans le tuto et je te remercie d'insister là-dessus.
Pour répondre à tes questions, pierre_24, cet algo est efficace à certaines conditions. Comme l'a évoqué bluestorm, prendre le pivot aléatoirement est la bonne chose à faire et garantit un exécution en O(n*log n), tout comme le tri fusion.
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
|
dont ask to ask
Groupe : Anciens
|
Citation Comme l'a évoqué bluestorm, prendre le pivot aléatoirement est la bonne chose à faire et garantit un exécution en O(n*log n), tout comme le tri fusion.
Faux. Il ne "garantit" rien du tout, il rend juste le cas pathologique très différent des cas pathologiques habituels et prédictibles. Même avec un pivot randomisé tu peux tomber sur un pire cas avec un nombre quadratique de comparaisons.
Encore une fois, cette formulation de ta part (vraie erreur ou maladresse de formulation ? ça commence à arriver un peu trop souvent pour que la maladresse soit crédible à chaque fois) trahit un problème.
Citationje ne vois pas en quoi s'appuyer sur des démonstrations mathématiques pose problème et même si l'on a sois-même du mal à les comprendre
Si on n'est pas capable d'utiliser des outils formels sans dire des bêtises, on ne les utilise pas. C'est du bon sens.
Moi aussi, il y a des outils formels que je ne comprends pas, ou pas assez bien, et j'évite d'en parler quand je suis censé enseigner quelque chose de solide aux gens. C'est le cas de tout le monde, et il suffit de connaître ses limites.
Mon avis, c'est juste que le concept de "complexité moyenne" et tout ce qui l'entoure est juste trop compliqué, en l'état, pour être utilisé comme tel dans un tuto d'algo sur le SdZ. Ça repose sur des notions techniques délicates, et il n'y a aucune chance d'apporter des connaissances solides aux gens en les utilisant.
Je ne sais pas pourquoi tu t'obstines à essayer d'en parler, mais de toute évidence ça ne marche pas (cf. les questions de pierre_24 qui rentrent exactement dans le cadre que je décris, où le nébuleux "cas moyen" ne sert à rien et on parle bien d'efficacité "en pratique", dans sa pratique à lui).
Si on pouvait s'en tenir à la complexité dans le pire cas (concept très abordable pour de nombreux algorithmes), et l'expérience pratique commune des programmeurs (c'est encore mieux quand elle est sourcée, d'ailleurs), quitte à mentionner discrètement des résultats théoriques plus poussés pour ceux qui en redemandent, ce serait mieux. Mais il s'agit de les mentionner rapidement pour seulement une partie des lecteurs, pas d'insister comme un éléphant dans une crèmerie en plein milieu du tuto, au risque de faire en fait comprendre des bêtises aux gens.
On pourrait écrire un tuto spécifique sur la complexité moyenne, qui rentre dans toutes ces subtilités, pas forcément de manière complètement formelle, pour les faire comprendre aux zéros très motivés. Pour cela, il faudrait bien maîtriser le sujet, et honnêtement je ne m'en sens pas capable actuellement (je pourrais le faire mais il faudrait que je me replonge dans tous ces trucs, c'est pas simple et ça m'intéresse pas vraiment). Si quelqu'un d'autre est motivé, pourquoi pas, mais ce n'est pas un sujet à prendre à la légère.
|
Faisons semblant
|
Edit : par MP, pour éviter deux pages de débats comme ça.
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
|
|
|
Citation : bluestorm Un autre tri assez utilisé est le tri par tas; une bonne implémentation est aussi rapide, voire plus rapide que le tri rapide, mais elle est un plus compliquée et difficile à comprendre
Perso je trouve que le tri par tas est plus simple à comprendre et à mettre en œuvre, enfin chacun son truc...
Cependant, j'ai toujours cru que le QSort était le tri qui donnait les meilleures performances une fois implémenté (je ne parle pas des pires cas). Si, comme tu le dis, le tri par tas offre des performances similaires ou meilleures, pourquoi dans les langages offrant des fonctions de tri pré-impémentées, l'algo utilisé est quasiment toujours le QuickSort ? (je ne met pas en doute tes dires, c'est juste une question naïve)
|
|
|
ça serait bien de préciser dans le titre que le 'Q' de QSort n'a rien à voir avec le la plateforme Qt (QSort qu'on pourrait confondre avec une fonction de base de la librairie Qt où quasiment tout commence par la lettre 'Q')..
|
Faisons semblant
|
quark : le tri rapide est plus rapide (grossièrement sur tout tableau qui ne provoque pas de n² et qui ne s'en rapproche pas) que le tri par tas en pratique pour des raisons de cache, si j'ai bonne mémoire (merci bluestorm ^^). C'est la conception de ton ordinateur qui fait cette supériorité et c'est sans doute la raison pour laquelle on le retrouve plus souvent que le tri par tas. Bon après, le std::sort de l'implémentation de la STL (C++) que je possède n'est pas un tri rapide pur mais une ingénieuse combinaison tri de sedgewick - tri introspective (et std::sort est donc toujours en O(n log n)).
« Sex, drugs and rock n'roll... enlevez la drogue et vous aurez plus de temps pour les deux autres »
Steven Tyler, Aerosmith
|
|
|
Merci pour ta réponse ShareMan
Citation : ShareManle tri rapide est plus rapide [...] que le tri par tas en pratique pour des raisons de cache
C'est justement ce que je pensais. Pourtant, bluestorm à l'air de dire qu'une bonne implémentation du tri par tas est au moins aussi rapide que le QuickSort. C'est pour ça que je suis un peu étonné...
|
|
|
Hello !
Je viens de lire le tuto, je l'ai trouvé vraiment bien pour l'explucation du principe mais plutôt brouillon dès que la notion de complexité a été abordée (n'ayant pas fait d'etudes en informatique, je découvre cette notion seul... et j'ai encore du mal à tout bien saisir mais bon, ça viendra)
Dans mes archives, j'ai un vieux bouquin de BASIC où il y a une implémentation du QuickSort.
Le pivot est choisi entre la première, la dernière valeur du tableau et celle du milieu il me semble (je vais recherche ce bouquin pour en être sur et voir comment il la choisit).
Ensuite il me semble aussi que la fin du tri était fait avec un tri par insertion ou quelque chose comme ça...
Bref, je cherche ça et je poste, si c'est vraiment intéressant, l'algorithme.
Édit:
Re ! (mes archives étaient bien mieux rangées que ce que je croyais  ).
Alors, les deux points dont je parlais :
- le choix du pivot.
Trois valeurs sont comparées : b (1er indice du tableau), m (indice du mileu du tableau) et h (dernier indice du tableau).
1) b et m sont comparés, le plus grand va en b, i=0,
2) h et b sont comparés, le plus grand va en h, dans ce cas i=1,
3) si i=1, on refait 1).
- la fin du tri.
Le choix est donné à l'utilisateur de la longueur des listes "petites" (celles à partir desquelles ont change d'algorithmes de tri) et de l'algorithme de tri utilisé (dans ce cas RipleSort - tri par échange - ou InsertionSort - tri par insertion  -).
"L'informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes." Michael R. Fellows et Ian Parberry
Si tu ne sais pas : demande, si tu sais : partage !
|
putain 16 ans
Ville : Tunis
Pays : Tunisie
|
excellent
par contre pour l'implémentation en C je ne suis pas trop convaincu.
j'ai essayé une approche similaire en pascal sur certains tableaux (contenu aléatoire), le code plante dans certains cas et dans d'autre produit un résultat erroné.
je propose une amélioration du code :
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | void quickSort (int t[], int deb, fin) {
int i = deb + 1,
j = fin ;
// la variable pivot est inutile vue qu'il ne change qu'à la fin du traitement
if (deb >= fin) return ;
while (deb < fin) {
while ((i<j)&&(t[deb]<t[i])) i++ ; // il faut modifier les conditions
while ((i<j)&&(t[deb]>t[j])) j-- ;
if (i<j) {
echanger (t, i, j) ; // il faut incrémenter et décrémenter
i++ ; // à chaque permutation
j-- ;
}
if (t[j]<t[d]) echanger (t, j, d) ;
quickSort (t, deb, j-1) ;
quickSort (t, j, fin) ;
}
|
en espérant que ça puisse aider 
edit :
il faut aussi prendre en compte que le pivot une fois permuté n'est pas à sa place définitive, on divise le tableau en deux et on refait jusqu'à tomber sur un singleton.
En plus ce code ne sert qu'à trier par ordre croissant, pour le faire décroissant il faut inverser les boucles et les conditions
|
bluestorm
Trouvez une formation
Suggestions
Twitter
Facebook
Google+