« 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>
|