(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 92 on page 385
   Quicksort on arrays *)

  let swap a i j =
    let t = a.(i) in 
    a.(i) <- a.(j); 
    a.(j) <- t

  let partition a l r =
    let p = a.(l) in
    let m = ref l in
    for i = l + 1 to r - 1 do
      if le a.(i) p then begin incr m; swap a i !m end
    done;
    if l <> !m then swap a l !m;
    !m

  let rec quick_rec a l r =
    if l < r - 1 then begin
      let m = partition a l r in
      quick_rec a l m;
      quick_rec a (m + 1) r
    end

  let quicksort a = quick_rec a 0 (Array.length a)
  

This document was generated using caml2html