Dutch Partition

Van C. Ngo · October 30, 2016

This post describes the implementation of the Dutch partition problem using OCaml such that the memory space complexity is constant.


The Dutch partition arises when we want to optimize the quick sort: given an array A whose elements are comparable and an index i of an element in the array. Reorder the array such that the initial elements are smaller than A[i], and are followed by elements that equal to A[i], the final elements are bigger than A[i], using constant memory space complexity \(O(1)\).

I implement the problem using OCaml. The main idea is the use of 3 flags to determine the 3 regions above.

  • A[0 .. smaller-1] : smaller region
  • A[smaller .. equivalent-1] : equivalent region
  • A[equivalent .. larger] : unclassified region
  • A[larger+1 .. size-1]: larger region

The “smaller” and “equivalent” flags are initialized 0 and “larger” is initialized (size - 1). That means at the beginning the whole array is unclassified. We use a recursive function to reduce the number of elements in unclassified region is 0.


The source code is given as follows.

let swap i j a =
    let tmp = a.(j) in
    a.(j) <- a.(i);
    a.(i) <- tmp; a
    _ -> raise (Invalid_argument "out-of-range")
(* auxiliary function *)
(* a[0 .. smaller - 1] : smaller region
   a[smaller .. equivalent - 1] : equivalent region
   a[equivalent .. larger] : unclassified region
   a[larger + 1 ... size - 1] : larger region
let rec partition smaller equivalent larger pivot a =
  if equivalent <= larger then
        if a.(equivalent) < pivot then
          (* put a.(equivalent) to the smaller region *)
          partition (smaller+1) (equivalent+1) larger pivot (swap smaller equivalent a)
          if a.(equivalent) = pivot then
            (* move to the next element in the unclassified region *)
            partition smaller (equivalent+1) larger pivot a
            (* move a.(equivalent) to the larger region *)
            partition smaller equivalent (larger-1) pivot (swap equivalent larger a)
        _ -> raise (Invalid_argument "out-of-range")

let dutch_partition pivot_index a =
    partition 0 0 (pred (Array.length a)) (a.(pivot_index)) a
    _ -> raise (Invalid_argument "out-of-range")

open Printf               
(* test *)               
let _ =
  Array.iter (printf "%d; ") (dutch_partition 3 [|0;1;9;9;9;9;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19|])