Efficient Ocaml Operating System

Question

I would like to know how to write an effective version of quicksort where the list is split in one go .

I have this piece of code,

let rec quicksort' = function [] -> [] | x::xs -> let small = List.filter (fun y -> y < x ) xs and large = List.filter (fun y -> y > x ) xs in quicksort' small @ (x :: quicksort' large);; 

but here I go through the list more than once (call 2 times quicksort for small and large).

The idea is to do this in just one step , without going to the list more than once.

Answer 1

List.partition is the way to go:

 let rec quicksort = function | [] -> [] | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs in quicksort smaller @ (x::quicksort larger) 

Note that List.partition helps avoid one redundant crawl through xs . You still have to sort the smaller part and the larger part recursively, since this works with Quicksort.

I have to say that this version of quicksort is far from efficient. Quick Sort Algorithm is a built-in algorithm that recursively mutates an input array. Another factor is the choice of vertices; choosing the first element, since the anchor point is not always a good idea.

These factors lead to extremely different implementation implementations (possibly using Array and mutation). Quicksort on a List should be used to demonstrate the idea of ​​an algorithm and the beauty of its recursion.

Answer 2

If you need to write an effective sorting function, you can read this insightful article: Engineering sorting function . Otherwise, I'm sure List.sort is also well written.