Quick Sort

Definition

Quick sort sorts an array based on a divide, conquer strategy (actually, more like conquer and then divide). Quick sort works by recursively partitioning an array. In each partitioning step we choose a pivot and then move all the numbers less than the pivot to the left and all the numbers greater than the pivot to the right. Then we stick the pivot right between these two sides of the array as a partition (mechitza). At this point the pivot is in its final resting place in the array (R.I.P.) and we can consider conquered. We now divide the array by recursively calling quick sort on the left and right sides of the partition (making sure to leave the partition out because it is already sorted).

Partition

Partitioning works as follows:

  1. A random element of the array ( usually the first), is selected to be the pivot.
  2. It puts every number less than the pivot on the left side of the array, and every number greater than the pivot on the right side of the array.
  3. It puts the pivot in its place, between the numbers higher than it and those lower than it.

Pivot Selection

The perfect pivot to choose would be the median of the array but you don't want to keep looping through the array to find the median and waste time. There are a number of different ways to select pivots, but they each have their pros and cons.

  1. Use a random element in the array.
  2. Use the median of the first, middle, and last element in the array as the pivot.
  3. Use either the first or last element as the pivot.

Finding the median of the first, middle and last element in an array decreases the chance that you will end up with the worst case scenario, but it still is possible to have a pretty bad runtime.

Code

public static void quicksort(int[] arr, int start, int end){
    if(start < end){
        int pivot = partition(arr,start,end);
        quicksort(arr,start,pivot - 1);
        quicksort(arr,pivot + 1,end);
    }
}
 
public static int partition(int[] arr, int start, int end){ 
    int high = end; 
    int low = start + 1; 
    int pivot = start; 
    while (high >= low){ 
        while (low <= end && arr[low] <= arr[pivot]){  
            low++;                                    
        } 
        while (high >= start + 1 && arr[high] >= arr[pivot]){ 
            high--;                                        
        }                                       
        if(high > low){ 
            swap(arr, low, high); 
        } 
    } 
    swap(arr, pivot, high); 
 
    return high; 
}

Visual

flickr:3036962256

Runtime

Quicksort runs on average O(nlogn), but is usually faster than other O(nlogn) algorithms such as Mergesort. This is because Quicksort does not need to keep creating new arrays thus saving time and space. It also saves time by not having to put the array back together at the end.

Worst Case

The worst case is when quicksort recursively partitions the array into pieces that are of size 1 and n-1(for example, when the array is already sorted, and the pivot is the smallest or greatest number). In this case, quicksort is basically doing a very slow selection sort, making it run O(n2).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License