Quicksort in notes

2022-03-02

Quicksort

Quicksort is an efficient, easy-to-implement in-place sorting algorithm. The average case for quicksort is O(n log n). Although merge sort is a better candidate when we take the worst-case complexity of Quicksort into account. However, quicksort has a smaller constant than mergesort, making it a better candidate for some cases.

The algorithm is as follows:

A pivot is chosen. The pivot is a number from the array.
The array is rearranged. Elements smaller than the pivot are on the left side of the array and elements bigger than the pivot are moved to the right.
After each iteration the pivot finds its suitable place.
The left side of the array is sorted recursively.
The right side of the array is sorted recursively.

If we translate the above steps to code.

package quicksort

func Quicksort(arr []int) []int {
	return quicksort(arr, 0, len(arr)-1)
}

func quicksort(arr []int, l, h int) []int {
	if l < h {
		k := partition(arr, 0, h)
		quicksort(arr, 0, k-1)
		quicksort(arr, k+1, h)
	}

	return arr
}

Clearly partition function is doing the magic.

Variants of partition

The most common implementations of partition are Lomuto partition scheme and Hoare partitio scheme.

Hoare partition scheme

func partition(arr []int, lb, ub int) int {
	pivot := arr[lb] // Choose the first element of array as pivot

	// start and end are pointers beginning at the lower and upper bounds of the array
	start, end := lb, ub
	for {
		// stop iterations if pointer cross each other.
		if start > end {
			break
		}

		// keep moving the start pointers towards right
		// until an element bigger than pivot is found.
		for arr[start] <= pivot {
			start++
		}

		// move end pointer towards left of the array
		// until element smaller than pivot is found.
		for arr[end] > pivot {
			end--
		}

		// swap the element of the array pointed by start and end.
		arr[start], arr[end] = arr[end], arr[start]
	}

	// swap the pivot to start pointer position.
	arr[lb], arr[start] = arr[start], arr[lb]

	return start
}

Lomuto partition scheme

This is a simpler implementation of the partitioning function.

func partition(arr []int, lb, ub int) int {
	pivot := arr[ub]

	i := lb
	for j := lb; j < ub; j++ {
		if arr[j] <= pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}

	arr[i], arr[ub] = arr[ub], arr[i]

	return i
}

TODO: This is actually not sorting elements properly.