## Sunday, June 10, 2018

### Bucket Sort

Bucket Sort

Bucket sort assumes input generated by a random process that distributes elements uniformly over the interval [0, 1).

The idea of bucket sort is to divide [0, 1) into n equal-sized subintervals or buckets, and then distribute the n input numbers into the buckets. To produce the output, sort the numbers in each bucket and then go through the buckets in order. Sorting a bucket can be done with insertion sort.

let rec insert x = function
| [] -> [x]
| h :: tl as ls ->
if x < h then x :: ls else h :: insert x tl

let rec insertion_sort = function
| [] | [_] as ls -> ls
| h :: tl -> insert h (insertion_sort tl)


This code for bucket sort assumes the input is an n-element array a and that each element 0 ≤ a.(i) < 1. The code requires an auxillary array b.(0 .. n - 1) of lists (buckets).

let bucket_sort a =
let n = Array.length a in
let b = Array.make n [] in
Array.iter
(fun x ->
let i =
int_of_float (
floor (float_of_int n *. x)
) in
Array.set b i (x :: Array.get b i)
) a;
Array.iteri
(fun i l ->
Array.set b i (insertion_sort l)
) b;
Array.fold_left (fun acc bucket -> acc @ bucket) [] b
;;
bucket_sort [| 0.78; 0.17; 0.39; 0.26; 0.72; 0.94
; 0.21; 0.12; 0.23; 0.68|]

Bucket sort runs in linear time on the average.

References:
[1] "Introduction to Algorithms" Section 9.4:Bucket Sort -- Cormen et. al. (Second ed.) 2001.