:PROPERTIES:
:ID: f37ce2ed-27c4-4208-8995-e45e6ae49801
:mtime: 20231023023523 20231016022745
:ctime: 20231016022730
:END:
#+title: quicksort
#+filetags: :public:project:
* Definition
Quicksort is an algorithm for [[id:9c2f8198-fead-4602-aa99-8f5312e239fb][Sorting a List]].
** Ocaml implementation of quicksort
#+BEGIN_SRC ocaml
let rec quicksort = function
| [] -> []
| x :: xs ->
let rec partition left right = function
| [] -> (quicksort left) @ [x] @ (quicksort right)
| y :: ys -> if y <= x then partition (y :: left) right ys else partition left (y :: right) ys
in
partition [] [] xs
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
quicksort [ 4 ; 3 ; 5 ; 1 ; 5; 7 ; 123 ; 21 ; 4]
#+END_SRC
#+RESULTS:
| 1 | 3 | 4 | 4 | 5 | 5 | 7 | 21 | 123 |
* Asymptotic Complexity
The space complexity of quicksort is $O(1)$.
The average time complexity of quicksort is $O(n\log n)$.
The worst-case time complexity of quicksort is $O(n^{2})$.
The worst case for quicksort is if the paritition element always chooses
an extreme case.