Quick Sort

This sort is fast and does not have the extra memory requirements of MergeSort. On average its run time is $O (n~log~n)$ but it does have a worst case run time of $O(n^2)$

The quick sort algorithm is a divide and conquer strategy where it will partition an array into 3 parts: - all values smaller than a pivot value (more on this later), the pivot, and all values larger than the pivot value

This partitioning algorithm is very fast and has an O(n) run time where n is the size of the original partition.

By partitioning the array in this manner we are splitting a large array into 3 pieces. The pivots are correctly placed in the array. All values smaller than the pivot are in the front part of the array. All values larger than pivot come after the pivot.

This partitioning algorithm is then applied to the parts that are smaller/bigger than pivot. The pivot is in the right place so no need to move it.

Once the partition is small enough, insertion sort is used to sort the very small arrays. The point at which the partition becomes "small enough" is dependent on the compiler but it is somewhere around the 16 to 32 element element range.

Algorithm:

Partitioning Algorithm

1. Select a pivot. This pivot must be part of the partition. The pivot is to be chosen randomly from the the values within the partition.
2. Move the pivot out of the way by swapping it with the value at the end of the partition.
3. Go through list starting at the beginning. track the "end" of the smaller partition. This is initially set to being 1 before start index of the partition
4. Every time you come across a value that is smaller than the pivot you advance the "end" of the smaller partition by 1 and swap the value with whatever is there. This will effectively place all values smaller than pivot at the front of the array

Quick Sort Algorithm

1. if list is small, perform insertion sort. This is the base case
2. if the list is not too small, partition the list using the partitioning algorithm described above. This will split the list into 3 pieces, all values smaller than the pivot, the pivot, values greater than pivot
3. quick sort the piece that is smaller than pivot and the piece that is larger than the pivot.

Implementation

The implementation of quick sort has 4 components. Each of these are detailed below

quick sort

This function is similar in nature to the merge sort function. Its job is to provide a simple interface to the user. The actual work is done in the recursive quicksort function

Python

def quick_sort(mylist):
    recursive_quick_sort(mylist, 0, len(mylist) - 1)  # call recursive quicksort

C++

void quickSort(int arr[],int size){
   quickSort(arr,0,size-1);
}

Recursive Quicksort

This is the recursive quick sort algorithm. THRESHOLD is a constant. When a partition's size falls below the THRESHOLD value, insertion sort is performed. This serves as the base case for recursive quick sort.

If the partition size is larger than the threshold, we pick partition the array, returning the location of the pivot. After this, we quick sort the remaining parts of the array.

Python

def recursive_quick_sort(mylist, left, right, THRESHOLD=32):
    if right - left <= THRESHOLD:
        insertion_sort(mylist, left, right)
    else:
        pivot_position = partition(mylist, left, right)
        recursive_quick_sort(mylist, left, pivot_position - 1)
        recursive_quick_sort(mylist, pivot_position + 1, right)

C++

void quickSort(int arr[], int left, int right){
   if(right-left <= THRESHOLD){
      insertionSort(arr,left,right);
   }
   else{
      int i = partition(arr,left,right);
      quickSort(arr,left,i-1);
      quickSort(arr,i+1,right);
   }
}

insertion sort

This is a modified version of the insertion sort algorithm. Instead of sorting the entire list, it sorts a piece of the list as defined by the indices passed to the function

Python

def insertion_sort(mylist, left, right):
    for i in range(left + 1, right + 1):
        curr = mylist[i]  # store the first number in the unsorted part of
                          # of array into curr
        j = i
        # this loop shifts value within sorted part of array to open a spot for curr
        while j > left and mylist[j - 1] > curr:
            mylist[j] = mylist[j - 1]
            j = j - 1
        mylist[j] = curr

C++

/*performs the insertion sort algorithm on array from index left to index right inclusive.*/
void insertionSort(int arr[],int left,int right){
   int curr;
   int i, j;
   for(i=left+1;i<=right;i++){
      curr=arr[i];
      for(j=i;j>left && arr[j-1] > curr;j--){
         arr[j]=arr[j-1];
      }
      arr[j]=curr;
   }
}

Partitioning Function

This is the fast partitioning algorithm that splits up the array according to a pivot value

Python

import random

def partition(mylist, left, right):
    # choose a random index between left and right inclusive
    pivot_location = random.randint(left, right)

    # get the pivot
    pivot = mylist[pivot_location]

    # move the pivot out of the way by swapping with
    # last value of partition.  This step is crucial as pivot will
    # end up "moving" if we don't get it out of the way which will
    # lead to inconsistent results.
    mylist[pivot_location] = mylist[right]
    mylist[right] = pivot

    end_of_smaller = left - 1

    # note the loop below does not look at pivot which is in mylist[right]
    for j in range(left, right):
        if mylist[j] <= pivot:
            end_of_smaller += 1
            mylist[end_of_smaller], mylist[j] = mylist[j], mylist[end_of_smaller]

    # restore the pivot
    mylist[end_of_smaller + 1], mylist[right] = mylist[right], mylist[end_of_smaller + 1]

    # and return its location
    return end_of_smaller + 1

C++

int partition(int array[],int left, int right){

  //choose a random index between left and right inclusive
   int location = left + (rand()%(right-left+1));

   //get the pivot
   int pivot = array[location];

   //move the pivot out of the way by swapping with
   //last value of partition
   array[location] = array[right];
   array[right] = pivot;            //move the pivot out of the way


   int i=left-1;
   for(int j=left;j<right;j++){
      if(array[j]<=pivot){
         i=i+1;
         int tmp=array[i];
         array[i]=array[j];
         array[j]=tmp;
      }
   }

   //restore pivot so that it is just after i
   int tmp=array[i+1];
   array[i+1]=array[right];
   array[right]=tmp;
   return i+1;
}