CODEWITHSUNDEEP
functional-programmingocaml
Jackson Tale
Jackson Tale

Reputation: 25812

Any better way to implement quicksort in ocaml?

I implemented quicksort in OCaml. Here is the code:

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond;;

let partition = function
  | [] -> ([], [], [])
  | pivot::tl ->
    let rec p (left, right) = function
      | [] -> (left, right, [pivot])
      | first::rest ->
    let c = compare pivot first
    in 
    if c > 0 then
      p (first::left, right) rest
    else 
      p (left, first::right) rest
    in
    p ([], []) tl;;

let quicksort l =
  let sl = shuffle l 
  in
  let rec qs = function
    | [] -> []
    | l ->
      let (left, right, pivot) = partition l
      in 
      (qs left) @ pivot @ (qs right)
  in 
  qs sl;;

First, I think maybe there is a better way to implement partition. List.partition came to my mind, but I just wanted to implement the key part by myself

Second, I use @ a lot in the sorting which is inefficient, right?

any suggestions?

Edit

One more question to think about is whether 3-way quicksort affects the implementation in OCaml?

Upvotes: 1

Views: 585

Answers (2)

rgrinberg
rgrinberg

Reputation: 9878

A micro optimization that you can try is to do List.concat[[qs left]; [pivot]; [qs right]] to append the lists at once buth you will need to run some benchmarks to verify this even helps.

Upvotes: 2

gasche
gasche

Reputation: 31459

The p function is badly indented; speaking of indentation, I tend to think the style of having a in on the next line is overkill for single-line declarations, so I'd rather put them at the end of the one-liner declaration.

More importantly, there is no need for it to take a tuple of lists as arguments, you'll have something syntactically lighter using two separate (curried) arguments. You could also use the List.partition function of the standard library.

Upvotes: 2

Related Questions