# Quicksort

Jump to navigation
Jump to search

Sorting
| |

Algorithms
| |

Bubble sort | |

Insertion sort | |

Selection sort | |

Quicksort | |

Merge sort | |

Heap sort | |

Introsort | |

Counting sort | |

Problems
| |

Problems solvable using sorting |

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

## Algorithm[edit]

- 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 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.

## Pseudocode[edit]

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{ swap(A[i], A[leftwall + 1]) leftwall = leftwall + 1 } } swap(pivot,A[leftwall]) return (leftwall)}

## Alternative definition in Common Lisp[edit]

(define q-sort (l &optional (f #'<)) (if (null (cdr l)) l (append (q-sort (remove-if-not #'(lambda (x) (funcall f x (car l))) (cdr l)) f) (list (car l)) (q-sort (remove-if #'(lambda (x) (funcall f x (car l))) (cdr l)) f))))