quick sort

Work in Progress

Summary

Quick sort

comparison based
divide-and-conquer
in-place (partitioning in array)
not stable (depends on partition strategy)
recursive

Time complexity

average case: - array is split roughly in half
already sorted: - bad pivot choice, pivot is max/min
many duplicates: - duplicates skew more elements to the right of the pivot

randomized

Loop invariant

at each partition, the pivot is moved to its final position

Blackbox sort

Arrays.sort()
- dual-pivot quick sort for primitive types

Concept

Algorithm

choose a pivot element
partition the array so elements smaller than pivot go left, larger go right
recursively quicksort the left and right partitions

java

private static void quickSort(int a[], int L, int R) { // ideally log N times, but might be N times
	if (L < R) {
		int p = partition(a, L, R); // O(n)
		// log n depth
		quickSort(a, L, p-1);
		quickSort(a, p+1, R);
	}
}

fast in practice, but worst-case needs mitigation (random pivot or median-of-3)

Partitioning

java

private static int partition(int a[], int i, int j) {
	int p = a[i]; // first element is the pivot
	int m = i;
	for (int k = i+1; k <= j; ++k) {
		if (a[k] < p) { // swap smaller elements into the left of the moving pivot
			++m;
			swap(a, k, m);
		} // notice that we do nothing when a[k] > p, because the swap handles it for us
	}
	swap(a, i, m); // swap pivot into its final position
	return m; // return the index of pivot, to be used by Quick Sort
}

Randomized quick sort

randomized pivot selection, handle sorted/nearly sorted
randomized duplicate handling, handle many duplicates

java

private static int partition(int a[], int i, int j) {
	// choose a random element to be the pivot
	Random rand = new Random();
	int r = i + rand.nextInt(j-i+1); // a random index between [i..j]
	swap(a, i, r);

	int p = a[i];
	int m = i;
	for (int k = i+1; k <= j; ++k) {
		if ((a[k] < p) || ((a[k] == p) && (rand.nextInt(2) == 0))) { // if equal to pivot, randomly decide if it goes left or right
			++m;
			swap(a, k, m);
		} 
	}
	swap(a, i, m); // swap pivot into its final position
	return m; // return the index of pivot, to be used by Quick Sort
}

Quickselect

rely on the loop invariant property of quick sort
look into the half that we expect the target value to be sorted into
abit like binary search that can be applied to an unsorted array

Application

Leetcode: kth-largest-element-in-an-array

use quickselect

java

public static int quickselect(int[] nums, int k, int lo, int hi) {
	int partition = partition(nums, lo, hi);

	if (partition == nums.length - k) 
		return nums[partition];
	else if (partition > nums.length - k)
		return quickselect(nums, k, lo, partition - 1);
	else
		return quickselect(nums, k, partition + 1, hi);
}

tikz