Implémentation d'algorithmes classiques/Algorithmes de tri/Tri rapide
Une mise en œuvre simple de QuickSort sur un tableau d'entiers en C :
int partitionner(int *tableau, int p, int r) {
int pivot = tableau[p], i = p-1, j = r+1;
int temp;
while (1) {
do
j--;
while (tableau[j] > pivot);
do
i++;
while (tableau[i] < pivot);
if (i < j) {
temp = tableau[i];
tableau[i] = tableau[j];
tableau[j] = temp;
}
else
return j;
}
}
void quickSort(int *tableau, int p, int r) {
int q;
if (p < r) {
q = partitionner(tableau, p, r);
quickSort(tableau, p, q);
quickSort(tableau, q+1, r);
}
}
Une mise en œuvre de quicksort sur un tableau de réels en Fortran, utilisant une fonction récursive. La liste à trier est stockée dans InList, et le résultat renvoyé dans OutList. L'utilisation de tableaux de taille implicite est ici un plus pour éviter les erreurs de segmentation lors de l'exécution.
recursive function QuickSort(InList) result(OutList)
REAL,DIMENSION(:) :: InList
REAL,DIMENSION(size(InList,1)) :: OutList
REAL,DIMENSION(size(InList,1)) :: SupList, OrderedSupList, InfList, OrderedInfList
REAL :: pivot
INTEGER :: i,j, InfListSize, SupListSize
! S'il ne reste qu'un élément dans la liste, on arrête la récursion
if(size(InList,1) < 2) then
OutList(1) = Inlist(1)
else
! Le pivot sera le premier élément de la liste
pivot = InList(1)
! On trie la liste
InfListSize = 0
SupListSize = 0
do i = 2, size(InList,1)
if(InList(i) < Pivot) then
InfListSize = InfListSize + 1
InfList(InfListSize) = InList(i)
elseif(InList(i) >= Pivot) then
SupListSize = SupListSize + 1
SupList(SupListSize) = InList(i)
end if
enddo
! On recompose la liste
if(InfListSize < 1) then
OrderedSupList = QuickSort(SupList(1:SupListSize))
OutList = (/ Pivot, (OrderedSupList(j), j=1,SupListSize) /)
elseif(SupListSize < 1) then
OrderedInfList = QuickSort(InfList(1:InfListSize))
OutList = (/ (OrderedInfList(j), j=1,InfListSize), Pivot /)
else
OrderedInfList = QuickSort(InfList(1:InfListSize))
OrderedSupList = QuickSort(SupList(1:SupListSize))
OutList = (/ (OrderedInfList(j), j=1,InfListSize), Pivot, (OrderedSupList(j), j=1,SupListSize) /)
endif
end if
end function QuickSort
Une implémentation au langage fonctionnel Haskell :
qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort (x:xs) = (qSort inf) ++ eq ++ (qSort sup)
where (inf,eq,sup) = separer x xs ([], [x], [])
where separer _ [] (i,e,s) = (i,e,s)
separer m (x:xs) (i,e,s)
| m > x = separer m xs (x:i,e,s)
| m == x = separer m xs (i,x:e,s)
| otherwise = separer m xs (i,e,x:s)
La fonction pourrait être améliorée par un pivot tiré au hasard.
Une version plus courte :
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (pivot:rest) = (quicksort [y| y<-rest, y<pivot]) ++
[pivot] ++
(quicksort [y| y<-rest,y>=pivot])
Java (ou C Sharp)
[modifier | modifier le wikicode]Une mise en œuvre simple de QuickSort (d'une manière récursive) sur un tableau d'entiers en Java ou en C Sharp :
public static void quicksort(int [] tableau, int début, int fin) {
if (début < fin) {
int indicePivot = partition(tableau, début, fin);
quicksort(tableau, début, indicePivot-1);
quicksort(tableau, indicePivot+1, fin);
}
}
public static int partition (int [] t, int début, int fin) {
int valeurPivot = t[début];
int d = début+1;
int f = fin;
while (d < f) {
while(d < f && t[f] >= valeurPivot) f--;
while(d < f && t[d] <= valeurPivot) d++;
int temp = t[d];
t[d]= t[f];
t[f] = temp;
}
if (t[d] > valeurPivot) d--;
t[début] = t[d];
t[d] = valeurPivot;
return d;
}
On trie t de l'indice 'debut' inclus à l'indice 'fin' inclus. Le pivot est toujours le premier élément du sous-tableau fourni à la procédure de partitionnement.
var t = [ ... ]; // le tableau est une variable globale
function executer_tri_rapide (debut, fin) {
if (debut < fin) {
var indice_pivot = partitionner(debut, fin);
executer_tri_rapide(debut, indice_pivot-1);
executer_tri_rapide(indice_pivot+1, fin);
}
}
function partitionner (debut, fin) {
var temp;
var valeur_pivot = t[debut], d = debut+1, f = fin;
while (d < f) {
while (d < f && t[f] >= valeur_pivot) f--;
while (d < f && t[d] <= valeur_pivot) d++;
temp = t[d];
t[d] = t[f];
t[f] = temp;
}
if (t[d] > valeur_pivot) d--;
t[debut] = t[d];
t[d] = valeur_pivot;
return d;
}
Implémentation du tri rapide en Kotlin.
fun partition(array: MutableList<Int>, start: Int, end: Int): Int {
var start = start
var end = end
while (start < end) {
while (start < end) {
if (array[start] > array[end]) {
val swap = array[start]
array[start] = array[end]
array[end] = swap
break
}
end -= 1
}
while (start < end) {
if (array[start] > array[end]) {
val swap = array[start]
array[start] = array[end]
array[end] = swap
break
}
start += 1
}
}
return start
}
fun quicksort(array: MutableList<Int>, start: Int = -1, end: Int = -1) {
var start = start
var end = end
if (start == -1) start = 0
if (end == -1) end = array.size
if (start < end) {
val i = partition(array, start, end - 1)
quicksort(array, start, i)
quicksort(array, i + 1, end)
}
}
(defun sort-gen (liste &optional (predicat #'<))
"Fonction de tri rapide généralisé"
(cond ((< (length liste) 2) liste)
((or (equal (remove-if-not (lambda (x) (funcall predicat x (car liste))) liste) liste)
(equal (remove-if-not (lambda (x) (funcall predicat x (car liste))) liste) '() )) liste)
(t (append (sort-gen (remove-if-not (lambda (x) (funcall predicat x (car liste))) liste) predicat)
(sort-gen (remove-if (lambda (x) (funcall predicat x (car liste))) liste) predicat)))))
Implémentation du tri rapide en Objective Caml en utilisant les listes chaînées. Le pivot choisi dans cette implémentation est toujours le premier élément de la liste.
let rec qsort = function
[] -> []
| pivot::reste -> let (petits, grands) = List.partition ((>) pivot) reste in
qsort petits @ [pivot] @ qsort grands
(* Type de List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list *)
La fonction List.partition sépare une liste en deux listes petits (éléments inférieurs au pivot) et grands (éléments supérieurs ou égaux au pivot).
On aurait pu définir et utiliser une fonction partition pour le cas particulier du tri rapide :
(* Type de partition : 'a -> 'a list -> 'a list * 'a list *)
let partition pivot liste =
let rec partitionR listePlusPetit listePlusGrand = function
[] -> (listePlusPetit, listePlusGrand)
| tete :: queue -> if tete < pivot then
partitionR (tete :: listePlusPetit) listePlusGrand queue
else partitionR listePlusPetit (tete :: listePlusGrand) queue
in partitionR [] [] liste
Une mise en œuvre simple de QuickSort sur un tableau d'entiers en Pascal :
const MAX_VAL = 200;
type tab_entier = array [1..MAX_VAL] of integer;
procedure tri_rapide(deb, fin : integer ; var t : tab_entier);
var
i, p : integer;
mid, aux : integer;
begin
(* si fin > deb alors le tableau nécessite d'être trié*)
if (fin > deb) then begin
(* choisir le milieu du tableau comme pivot *)
mid := (deb + fin) div 2;
(*
mettre l'élément pivot au début afin de pouvoir parcourir
le tableau en continu.
*)
aux := t[mid];
t[mid] := t[deb];
t[deb] := aux;
(*
parcourir le tableau tout en amenant les éléments infèrieurs à
l'élément pivot au début de la plage
*)
p := deb;
for i:=deb+1 to fin do
begin
if (t[i] < t[deb]) then
begin
p := p + 1;
aux := t[i];
t[i] := t[p];
t[p] := aux;
end;
end;
(*
mettre le pivot à la position adéquate càd
à la suite des éléments qui lui sont inférieurs
*)
aux := t[p];
t[p] := t[deb];
t[deb] := aux;
tri_rapide(deb, p - 1, t); (* trie le sous tableau à gauche *)
tri_rapide(p + 1, fin, t); (* trie le sous tableau à droite *)
end;
end;
On trie $t de l'indice $debut inclus à l'indice $fin inclus. Le pivot est toujours le premier élément du sous-tableau fourni à la procédure de partitionnement.
$t = array( ... ); // le tableau est une variable globale
function executer_tri_rapide ($debut, $fin) {
if ($debut < $fin) {
$indice_pivot = partitionner($debut, $fin);
executer_tri_rapide($debut, $indice_pivot - 1);
executer_tri_rapide($indice_pivot + 1, $fin);
}
}
function partitionner ($debut, $fin) {
global $t;
$valeur_pivot = $t[$debut];
$d = $debut + 1;
$f = $fin;
while ($d < $f) {
while ($d < $f && $t[$f] >= $valeur_pivot) $f--;
while ($d < $f && $t[$d] <= $valeur_pivot) $d++;
$temp = $t[$d];
$t[$d] = $t[$f];
$t[$f] = $temp;
}
if ($t[$d] > $valeur_pivot) $d--;
$t[$debut] = $t[$d];
$t[$d] = $valeur_pivot;
return $d;
}
Prolog
[modifier | modifier le wikicode]qsort([X|L],R,R0) :-
partition(L,X,L1,L2),
qsort(L2,R1,R0),
qsort(L1,R,[X|R1]).
qsort([],R,R).
partition([Y|L],X,[Y|L1],L2) :- Y=<X, partition(L,X,L1,L2).
partition([Y|L],X,L1,[Y|L2]) :- Y>X, partition(L,X,L1,L2).
partition([],_,[],[]).
Ici, nous avons une implémentation en Python, qui utilise un meilleur partitionnement :
def partition(array, start, end):
while start < end:
# au début de cette boucle, notre élément permettant la partition
# est à la valeur 'start'
while start < end:
if array[start] > array[end]:
array[start], array[end] = array[end], array[start]
break
end -= 1
# au début de cette boucle, notre élément permettant la partition
# est à la valeur 'end'
while start < end:
if array[start] > array[end]:
array[start], array[end] = array[end], array[start]
break
start += 1
return start
def quicksort(array, start=None, end=None):
"""Le plus rapide des tris par échanges pour la plupart des usages."""
if start is None: start = 0
if end is None: end = len(array)
if start < end:
i = partition(array, start, end-1)
quicksort(array, start, i)
quicksort(array, i+1, end)
Ruby
[modifier | modifier le wikicode]def qsort tab
if tab.size < 2 then tab else
pivot = tab.delete_at rand tab.length # Choix du pivot aléatoire
(qsort(tab.select{|x| x<pivot}) << pivot) + qsort(tab.select{|x| x>=pivot})
end
end