Quicksort

Quicksort is one of the most effective sorting algorithms which developed by British computer scientist Tony Hoare in 1959. Quicksort is a 'divide and conquer' algorithm that, on average, sorts n items in O(n log n) time, which make it one of the most preferred sorting algorithms in various programming languages, despite its worst-case time complexity being O(n^2).

Visualization

How Does It Work?

Quicksort operates by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

• Partitioning: Choose an element from the array to serve as a pivot and put the pivot in the right sorted position. Although there are many strategies to select the pivot, a common practice is to choose the last element in the array.

• Recursive Sort: Recursively apply the above steps to the left sub-array of elements with smaller values and to the right sub-array of elements with larger values. Do nothing if the sub-array contains only 1 or no element.

Strengths and Weaknesses

Quicksort's main strength lies in its efficiency in handling large datasets. The recursive approach, dividing the problem into smaller, simpler problems, is part of why Quicksort is effective. On average, it outperforms other popular sorting algorithms like Bubble Sort, Insertion Sort, and Selection Sort, especially for large arrays.

Quicksort is an in-place sorting algorithm, meaning it sorts the input array using a small, constant amount of extra space. Therefore, its space complexity is O(log n).

However, its performance is greatly influenced by the choice of the pivot. If the pivot is consistently the smallest or largest element, the partitioning will result in one very small and one very large sub-array, leading to its worst-case time complexity of O(n^2). This typically occurs when the input array is already sorted or sorted in reverse order.

To mitigate this issue, a technique known as 'median of three' may be used, where the pivot is chosen as the median of the first, middle, and last elements of the array. This strategy tends to produce more balanced partitions and brings the time complexity closer to the ideal O(n log n).

Application

Quicksort's efficiency makes it a preferred choice in many real-world applications. It is used in programming languages like C and Python for in-built sorting functions. Additionally, it plays a significant role in computer graphics for rendering, database management for query execution, and machine learning for data preprocessing, among others.

Implementation

// QuickSort sorts array of items
export function quickSort(a: number[]) {
	sort(a, 0, a.length - 1)
}

function swap(a: number[], i: number, j: number) {
	const tmp = a[i]
	a[i] = a[j]
	a[j] = tmp
}

function sort(a: number[], low: number, high: number) {
	if (low < high) {
		const pi = partition(a, low, high)
		sort(a, low, pi-1)
		sort(a, pi+1, high)
	}
}

function partition(a: number[], low: number, high: number): number {
	const pivot = a[high]

    // find first position i where a[i] >= pivot (could be pivot position itself)
	let i = low
	while (a[i] < pivot) {
		i++
	}

    // up to the position prior to the pivot, if found element smaller than pivot then move it to the left
	for (let j = i + 1; j < high; j++) {
		if (a[j] < pivot) {
			swap(a, i, j)
            i++
		}
	}

    // swap pivot with i
    if (i < high) swap(a, i, high)

	return i
}