wiki:Algorithms/QuickSort

Quick Sort

Declarative

fun quicksort [] = []
  | quicksort (x::xs) =
    let 
        val (left, right) = List.partition (fn y => y<x) xs
    in
        quicksort left @ [x] @ quicksort right
    end
qs (p:xs) = qs [x | x <- xs, x < p] ++ [p] ++ qs [x | x <- xs, x >= p]
import Data.List
 
qsort [] = []
qsort (p:xs) = qsort ys ++ p : qsort zs
      where (ys, zs) = partition (< p) xs

What if already sorted?

Never choose the first element of a list as a pivot. It will lead to O(n2) process.

Choose a mean of the three (first, middle, last) or any other scanning heuristic.

C

C++

Last modified 13 months ago Last modified on Jan 27, 2019, 5:15:10 AM
Note: See TracWiki for help on using the wiki.