Quick Sort is a popular sorting algorithm that is widely used in computer science. It is known for its efficiency and simplicity, and it is often used as a benchmark for other sorting algorithms.
The algorithm works 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.
Quick Sort was invented by Tony Hoare in 1959 and has since become a fundamental part of computer science.
Algorithm
Here is the algorithm for quick sort:
- Choose a pivot element from the array.
- Partition the array into two sub-arrays, according to whether they are less than or greater than the pivot element.
- Recursively apply the quick sort algorithm to each sub-array.
Partition
The partitioning process starts by selecting a pivot element from the array. There are different ways to choose a pivot element, but one common method is to select the last element of the array. The partitioning process then proceeds as follows:
- Initialize two pointers i and j. Pointer i starts from the beginning of the array and pointer j starts from the beginning of the array.
- Traverse the array with the j pointer, comparing each element with the pivot element.
- If an element less than to the pivot is encountered, swap it with the element at index i, and increment i. This ensures that all elements less than to the pivot are on the left of the pivot.
- Once j reaches the end of the array, swap the pivot element with the element at index i+1. This ensures that the pivot element is in its correct position in the array.
- Return the index of the pivot element.
At the end of the partitioning process, the array is partitioned into two sub-arrays around the pivot element. The left sub-array contains elements less than to the pivot, and the right sub-array contains elements greater than of equal to the pivot. These sub-arrays are then recursively sorted using the same partitioning process until the entire array is sorted.
The partitioning process is a key component of the QuickSort algorithm and has a time complexity of O(n), where n is the size of the array being partitioned. It is also a stable operation, which means that the relative order of equal elements is preserved after the partitioning process.
Implementation of Quick Sort in Python
from typing import List
def partition(arr: List[int], low: int, high: int) -> int:
"""Partitions the array into two sub-arrays.
Elements smaller than the pivot on the left and elements greater than the pivot on the right.
Args:
arr: The array to partition.
low: The starting index of the sub-array to partition.
high: The ending index of the sub-array to partition.
Returns:
The index of the pivot element.
"""
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort_inplace(arr: List[int], low: int, high: int) -> None:
"""Sorts the given array in-place using the quicksort algorithm.
Args:
arr: The array to sort.
low: The starting index of the sub-array to sort.
high: The ending index of the sub-array to sort.
"""
if low < high:
pivot = partition(arr, low, high)
quicksort_inplace(arr, low, pivot - 1)
quicksort_inplace(arr, pivot + 1, high)
arr = [11, 3, 14, 3, 10, 7, 8, 3, 1, 1, 1, 9, 1, 5]
quicksort_inplace(arr, 0, len(arr) - 1)
print("Sorted array:", arr)
Properties of Quick sort
-
Divide and Conquer
The key idea behind Quick Sort is the Divide and Conquer strategy. The algorithm selects a pivot element from the array and partitions 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 using the same algorithm. -
In-Place Sorting
Quick Sort is an in-place sorting algorithm, which means that it does not require any additional memory to perform the sorting. It sorts the array by moving elements around within the array itself, without creating any new data structures. -
Recursive
Quick Sort is a recursive algorithm, which means that it calls itself repeatedly on smaller and smaller sub-arrays until the base case is reached. In the case of Quick Sort, the base case is when the sub-array has fewer than two elements. -
Average and Worst-Case Time Complexity
The time complexity of Quick Sort is O(n log n) on average, where n is the length of the array. This means that the algorithm takes approximately n log n operations to sort an array of length n. However, in the worst case, when the pivot element is chosen poorly (for example, if the array is already sorted), the time complexity can be O(n^2). -
Best-Case Time Complexity
The best-case time complexity of Quick Sort is O(n log n), which occurs when the pivot element is chosen such that the two sub-arrays are of equal size.