Implémentation d'algorithmes classiques/Algorithmes de tri/Tri rapide

C

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);
    }
}

Fortran 95

Une mise en oeuvre 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

Haskell

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)

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;
}

Javascript

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;
}

LISP

(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)))))

OCaml

Implémentation du tri rapide en Objective Caml en utilisant les listes chainé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

Pascal

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;

PHP

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

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([],_,[],[]).

Python

Ici, nous avons une implémentation en Python, qui utilise un meilleur partitionnement :

def partition(array, start, end, compare):
    while start < end:
        # au début de cette boucle, notre élément permettant la partition 
        # est à la valeur 'start'
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            end = end - 1
        # au début de cette boucle, notre élément permettant la partition 
        # est à la valeur 'end'
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            start = start + 1
    return start

def quicksort(array, compare=lambda x, y: x > y, 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, compare)
        quicksort(array, compare, start, i)
        quicksort(array, compare, i+1, end)

Ruby

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

Tout ou partie de cette page est issue de l'article Wikipédia « Tri rapide » dans sa version du 27/04/2010.