« Implémentation d'algorithmes classiques/Algorithmes de tri/Tri rapide » : différence entre les versions

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;

}

}

 

== [[Programmation Fortran|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

end if

end function QuickSort

 

== [[Programmation Haskell|Haskell]] ==

Une implémentation au langage fonctionnel Haskell :

qSort :: Ord a => [a] -> [a]

qSort [] = []

| 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 [] = []

[pivot] ++

(quicksort [y| y<-rest,y>=pivot])

 

== [[Programmation Java|Java]] (ou [[Programmation C sharp|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) {

return d;

}

 

== [[Programmation Javascript|Javascript]] ==

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

 

return d;

}

 

== [[Programmation Lisp|LISP]] ==

(defun sort-gen (liste &optional (predicat #'<))

"Fonction de tri rapide généralisé"

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

 

== [[Objective Caml|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

[] -> []

qsort petits @ [pivot] @ qsort grands

(* Type de List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list *)

 

La fonction <code>List.partition</code> sépare une liste en deux listes <code>petits</code> (éléments inférieurs au pivot) et <code>grands</code> (é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 =

else partitionR listePlusPetit (tete :: listePlusGrand) queue

in partitionR [] [] liste

 

== [[Programmation Pascal|Pascal]] ==

Une mise en œuvre simple de QuickSort sur un tableau d'entiers en [[Pascal (langage)|Pascal]] :

 

const MAX_VAL = 200;

 

end;

end;

 

== [[Programmation PHP|PHP]] ==

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

return $d;

}

 

== Prolog ==

qsort([X|L],R,R0) :-

partition(L,X,L1,L2),

partition([Y|L],X,L1,[Y|L2]) :- Y>X, partition(L,X,L1,L2).

partition([],_,[],[]).

 

== [[Programmation Python|Python]] ==

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

 

def partition(array, start, end, compare):

while start < end:

quicksort(array, compare, start, i)

quicksort(array, compare, i+1, end)

 

== Ruby ==

def qsort tab

if tab.size < 2 then tab else

end

end

 

<small>Tout ou partie de cette page est issue de l'article Wikipédia « [[w:Tri rapide|Tri rapide]] » dans sa [{{fullurl:w:Tri_rapide|oldid=52570963}} version du 27/04/2010].</small>