dont ask to ask
Groupe : Membres
|
Un qsort simpe sur des listes, en OCaml :
Code : Ocamllet 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 : Ocamllet 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
|
Apprenez à utiliser la STL !!
Groupe : Membres
|
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
Groupe : Membres
|
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 .
|
"Se coucher tard nuit"
Groupe : Membres
|
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.
|
Groupe : Membres
|
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
Groupe : Membres
|
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.
|
PriPrOTtTt§!!!§
Groupe : Membres
|
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).
|
Groupe : Membres
|
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;
}
}
}
|
|
Tutoriels
Communauté
Mon compte
Recherche
Livre d'or
Publicité
bluestorm
429 Zéros connectés |
8 requêtes |
0.0251s (0.0138s)
