Aller au contenu

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

Un livre de Wikilivres.

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

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