Quick Sort

• Premise
  • Rearranges the array into two parts, called partitions
  • A pivot is selected and the following is executed
    • All elements less than the pivot are moved to the left
    • All elements greater than the pivot are moved to the right
  • The process is repeated until the array is sorted
• Process
  • Up pointer starts at pivot
  • Down pointer starts at end
  • They both move towards middle
    • Up finds something greater than pivot
    • Down finds something less
  • Swap those values
  • Repeat until the pointers pass each other, and then swap pivot and down (end of first pass here)
  • Repeat everything for both halves
• After the first pass, all elements on the left of the pivot are less and all to the right are greater

Implementation

void quickSort(int array[], int low, int high) {
	if (low < high) {
		int pivot = partition(array, low, high);
		quickSort(array, low, pivot - 1);
		quickSort(array, pivot + 1, high);
	}
}

• Different methods have different pivot functions
  • One of the best is the median element of the array
    • There is a method to find it in $O(\log \log n)$ time that is grad level
  • Ours is just pick the first element

int partition(int array[], int low, int high) {
	int pivot = array[low];
	int up = low;
	int down = high;
	
	while (up < down) {
		while ((up < high) && (array[up] <= pivot)) {
			up++;
		}
	
		while ((down > low) && (array[down] >= pivot)) {
			down--;
		}
	
		if (up < down) {
			swap(array[up], array[down]);
		}
	}
 
	swap(array[low], array[down]);
 
	return down;
}
 

Time Complexity

• $O(\log n)$ levels of recursion
• Partitioning requires $O(n)$ moves
• → $O(n\log n)$ average case