Quicksort

From Algorithmist

Quick sort is an efficient sorting algorithm invented by C.A.R. Hoare. Its average-case running time is $O (n log n)$ . Unfortunately, Quicksort's performance degrades as the input list becomes more ordered. The worst-case input, a sorted list, causes it to run in $O (n 2)$ time. An improvement upon this algorithm that detects this prevalent corner case and guarantees $O (n log n)$ time is Introsort.

1 Algorithm
2 Pseudocode
3 Alternative definition in Common Lisp
4 Implementations

[edit] Algorithm

Pick a "pivot point". Picking a good pivot point can greatly affect the running time.
Break the list into two lists: those elements less than the pivot element, and those elements greater than the pivot element.
Recursively sort each of the smaller lists.
Make one big list: the 'smallers' list, the pivot points, and the 'biggers' list.

Picking a random pivot point will not eliminate the $O (n 2)$ worst-case time, but it will usually transform the worst case into a less frequently occuring permutation. In practice, the sorted list usually comes up more often than any other permutation, so this improvement is often used.

[edit] Pseudocode

Quicksort(A as array, low as int, high as int)
    if (low < high)
        pivot_location = Partition(A,low,high)
    Quicksort(A,low, pivot_location - 1)
    Quicksort(A, pivot_location + 1, high)

Partition(A as array, low as int, high as int)
     pivot = A[low]
     leftwall = low

     for i = low + 1 to high
         if (A[i] < pivot) then
             leftwall = leftwall + 1
             swap(A[i], A[leftwall])
         swap(A[low],A[leftwall])

    return (leftwall)

[edit] Alternative definition in Common Lisp

(defun quicksort (lst)
  (when lst
    (let ((pivot (car lst)))
      (append
       (quicksort (remove-if-not (lambda (x) (<= x pivot)) (cdr lst)))
       (list pivot)
       (quicksort (remove-if-not (lambda (x) (>  x pivot)) (cdr lst)))))))