bouba
Junior Member 
Messages: 3
Inscrit(e) le: 28/09/2006
Déconnecté(e)
|
Publié le 28/09/2006 à 12:16 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
une URL vaut mieux qu'un long discours. 
http://www.gatago.com/comp/lang/ada/9580338.html
Le principe est de chosir une valeur pivot (en general on prend la premiere du tableau, mais on peut etre plus fin).
et de "couper" le tableau en deux parties (une pour les valeurs inferieures au pivot, l'autre pour les superieures), et
d'appliquer le tri sur les sous-tableau, et ainsi de suite. Il s'agit donc d'un algo de tri recursif.
A+ et encore desole pour l'archeologie, mais j'avoue, ce matin etait mortel a mon travail. ^^
Bouba |
ftbass
|
Publié le 28/09/2006 à 10:49 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
Très bien...
Peut-être peux-tu nous indiquer ce qu'est le tri rapide alors 
Merci
(Moi qui pensais que ce forum était mort ) |
bouba
Junior Member
Messages: 3
Inscrit(e) le: 28/09/2006
Déconnecté(e)
|
Publié le 28/09/2006 à 08:55 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
Bonjour,
Je suis desole de faire de l'archeologie, mais je cherchais des ressources Ada et je suis tombe ici. :)
Je suis un "ancien" du CNAM egalement, d'ou le fait que j'ai regarde les sujets (souvenirs, souvenirs).
Tout ca pour dire que l'algo presente ici n'est absolument pas un tri rapide!
Il s'agit d'un tri a bulles avec sa superbe complexite en O(n2) ...
Le tri rapide utilise le principe "diviser pour regner" et presente une complexite qui varie entre O(nlog(n)) et O(n2) en fonction de la
distribution initiale des donnees.
Si c'est un prof du CNAM qui a presente cela comme un "quicksort", alors ils ont bien change depuis le moment ou je les ai eu comme
prof. :-?
A+
Bouba |
ftbass
|
Publié le 05/10/2004 à 18:11 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
Pas de problème, ça m'a fait plaisir
N'hésite surtout pas si t'as des questions, ou des exos à proposer...
a++ |
DoubleTâche
Newbie
Messages: 1
Inscrit(e) le: 05/10/2004
Déconnecté(e)
|
Publié le 05/10/2004 à 14:13 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
merci pour toutes explications,j'étais bel et bien réveillée mais il me faut du temps pour comprendre !! |
ftbass
|
Publié le 01/10/2004 à 23:54 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
Tu ne dois pas être tres reveillé :)
t'as essayé de le compiler?
le tableau initial est :
Tab[1] = 0
Tab[2] = 3
Tab[3] = 8
la premiere case du tableau a pour indice 1
à la premiere itération de la boucle de tri, on a :
Tab[1] < tab[2] (0 < 3), donc on les permutte, on se retrouve avec le tableau suivant :
Tab[1] = 3
Tab[2] = 0
Tab[3] = 8
ici NbPermut vaut 1
on passe à i = 2
Tab[2] < tab[3] (0 < 8), donc on les permutte, on se retrouve avec le tableau suivant :
Tab[1] = 3
Tab[2] = 8
Tab[3] = 0
ici NbPermut vaut 2
On a fini le premier parcours du tableau, comme on a NbPermut > 0 on recommence le parcours
du tableau. On en profite pour remettre NbPermut à 0...
donc, 2e itération :
avec i = 1, on a :
Tab[1] < tab[2] (3 < 8), donc on les permutte, on se retrouve avec les 2 premieres cases du
tableau remplies comme ca :
Tab[1] = 8
Tab[2] = 3
Tab[3] = 0
ici NbPermut vaut 1
on passe à i = 2
Tab[2] > tab[3] (3 > 8), donc on NE les permutte PAS
NbPermut vaut tjrs 1, t le tableau est toujours le même:
Tab[1] = 8
Tab[2] = 3
Tab[3] = 0
On a fini le deuxieme parcours du tableau, comme on a NbPermut > 0 on recommence le
arcours du tableau. On en profite pour remettre NbPermut à 0...
On fait un dernier parcours du tableau. Pendant celui-ci, on a jamais tab[i] < tab[i+1],
donc NbPermut reste à 0, et on sort des boucles de tri... on passe à l'affichage... et on sort
du programme... :)
J'éspère que c'est plus clair (si je me suis pas embrouillé avec mes copier / coller)
a++, et bienvenue à toi :) |
tâche
Newbie
Messages: 1
Inscrit(e) le: 01/10/2004
Déconnecté(e)
|
 Publié le 01/10/2004 à 17:20 |
RE : Exo 5: Tri d'un tableau (tri rapide ou quick sort)
bonjour, je n'ai pas compris le raisonnement du tri, si je prends un tableau de 3 éléments dans l'ordre suivant: 0, 3, 8 je me retrouve
d'après ce que j'ai compris avec un tableau trié ainsi :3, 8 , 0;
je pourrais avoir d'avantage d'explications ? merci |
ftbass
|
Publié le 27/02/2004 à 22:01 |
Exo 5: Tri d'un tableau (tri rapide ou quick sort)
voici le code :
code:
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Nombres_aleatoires; use Nombres_aleatoires;
procedure QuickSort is
NbPermut : integer := 0;
Temp : integer;
Long : constant := 10;
Tab : Array(1 .. Long) of integer;
begin
randomize;
-- On remplit le tableau, et on affiche le tableau initial
for i in 1 .. Long loop
Tab(i) := random(20);
put(Tab(i), 4);
new_line;
end loop;
-- On trie
loop
NbPermut := 0;
for i in 1 .. (Long - 1) loop
if Tab(i) < Tab(i + 1) then
NbPermut := NbPermut + 1;
Temp := Tab(i);
Tab(i) := Tab(i + 1);
Tab(i + 1) := Temp;
end if;
end loop;
exit when NbPermut = 0;
end loop;
-- On affiche le tableau trié
new_line;
put("Une fois trie, le tableau devient :");
new_line;
for i in 1 .. Long loop
put(Tab(i), 4);
new_line;
end loop;
end; |
|
