# 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(n^{2}) process.

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

## C

## C++

Last modified
20 months ago
Last modified on Jan 27, 2019, 5:15:10 AM

**Note:**See TracWiki for help on using the wiki.