# Quick Sort

### From charlesreid1

# Notes

## Skiena Chapter 4

### Overview

Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting, and can implement quicksort recursively.

Quick sort is a *random* algorithm. Whenever we deal with a random algorithm, we always want to think about what the worst case scenario is, and what we can do to avoid it. In the case of quicksort, the worst case scenario consists of bad choices for each pivot - namely, each pivot that is chosen happens to be right next to the prior pivot, so we are continually sorting things one at a time, making quick sort equivalent to Insertion Sort.

In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).

However, in the worst case (which should happen very infrequently), quicksort is O(N^2).

### Algorithm

Here is a C implementation of quicksort:

quicksort(item_type s[], int lo, int hi) { int p; // index of partition if((hi-lo)>0) { p = partition(s, lo, hi); quicksort(s, lo, p-1); quicksort(s, p+1, hi); } }

This makes use of the following partition function:

int partition(item_type s[], int lo, int hi) { int i; // counter int p; // pivot element index int firsthigh; // divider position for pivot element // pivot equals s at hi p = hi; firsthigh = 1; for(i = 1; i < hi; i++) { if(s[i] < s[p]) { wswap(&s[i], &s[firsthigh]); firsthigh++; } } swap(&s[p], &s[firsthigh]); return( firsthigh ); }

# Flag

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |