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

Contenu supprimé Contenu ajouté
Déplacé une partie de code OCaml qui se trouvait en fin de page au lieu de la bonne section
Ligne 190 :
qsort petits @ [pivot] @ qsort grands
(* Type de List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list *)
</source>
 
La fonction <tt>List.partition</tt> sépare une liste en deux listes <tt>petits</tt> (éléments inférieurs au pivot) et <tt>grands</tt> (é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 :
<source lang="Ocaml">
(* 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
</source>
 
Ligne 335 ⟶ 348 :
end
end
</source>
 
La fonction <tt>List.partition</tt> sépare une liste en deux listes <tt>petits</tt> (éléments inférieurs au pivot) et <tt>grands</tt> (é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 :
<source lang="Ocaml">
(* 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
</source>