prof_simplet
Inscrit le: 12 Sep 2006 Messages: 86
|
Posté le: 26 Oct 2010 9:13 Sujet du message: tri rapide (QuickSort) |
|
|
Bonjour, voici une procédure de tri rapide (QuickSort) dichotomique.
Elle permet de trier une liste données de nombres.
Code: |
> tri_rapide:=proc(Z::list,l::posint,r::posint)
> local i,j,x,U;
> U:=Z;
> i:=l;j:=r;x:=U[iquo(l+r,2)];
> while evalb(i<=j) do
> while evalb(U[i]<x) do i:=i+1 end do;
> while evalb(x<U[j]) do j:=j-1 end do;
> if evalb(i<=j) then
> U:=subsop(i=U[j],j=U[i],U);
> i:=i+1:j:=j-1;
> end if;
> end do;
> if evalb(l<j) then U:=tri_rapide(U,l,j) end if;
> if evalb(i<r) then U:=tri_rapide(U,i,r) end if;
> U;
> end proc:
>
> L:=[seq(rand(1..100)(),k=1..100)];
L := [16, 98, 43, 53, 61, 47, 28, 75, 3, 5, 11, 37, 75, 4, 91, 22,
40, 58, 93, 98, 11, 30, 6, 32, 40, 24, 80, 96, 11, 23, 41, 52,
58, 67, 81, 65, 69, 2, 36, 61, 84, 96, 94, 31, 81, 31, 54, 67,
59, 66, 12, 49, 90, 35, 15, 26, 100, 24, 8, 63, 78, 23, 73,
22, 32, 98, 9, 53, 3, 98, 69, 3, 73, 88, 37, 60, 94, 52, 16,
29, 51, 3, 45, 67, 40, 71, 74, 49, 60, 69, 33, 30, 1, 83, 9,
64, 43, 57, 52, 62]
> tri_rapide(L,1,100);
[1, 2, 3, 3, 3, 3, 4, 5, 6, 8, 9, 9, 11, 11, 11, 12, 15, 16, 16, 22,
22, 23, 23, 24, 24, 26, 28, 29, 30, 30, 31, 31, 32, 32, 33,
35, 36, 37, 37, 40, 40, 40, 41, 43, 43, 45, 47, 49, 49, 51,
52, 52, 52, 53, 53, 54, 57, 58, 58, 59, 60, 60, 61, 61, 62,
63, 64, 65, 66, 67, 67, 67, 69, 69, 69, 71, 73, 73, 74, 75,
75, 78, 80, 81, 81, 83, 84, 88, 90, 91, 93, 94, 94, 96, 96,
98, 98, 98, 98, 100]
|
En espérant que cela sera utile à certains.
@+ |
|