Sorting algorithm based on Divide and Conquer computational paradigm
Advantages:
Main idea - partition around a pivot:
done in $O(n)$ time
partition:
QuickSort(array $A$):
Partition($A$):
running time $O(n)$ where $n = r - l + 1$
Quality
So, possible pivots
public void qsort(int[] input, int left, int right) { int n = right - left; if (n <= 1) { return; } int pivotIndex = partition(input, left, right); qsort(input, left, pivotIndex); qsort(input, pivotIndex + 1, right); } public int partition(int[] input, int left, int right) { int pivot = input[left]; int i = left + 1; for (int j = left + 1; j < right; j++) { if (input[j] < pivot) { swap(input, j, i); i++; } } swap(input, left, i - 1); return i - 1; } public void swap(int[] input, int j, int i) { int tmp = input[j]; input[j] = input[i]; input[i] = tmp; }
def pivot(A, l, r): return l def partition(A, l, r): pi = pivot(A, l, r) p = A[pi] A[l], A[pi] = A[pi], A[l] i = l for j in range(i + 1, r): if A[j] < p: i = i + 1 A[i], A[j] = A[j], A[i] A[l], A[i] = A[i], A[l] return i def qs(A, l, r): n = r - l if n <= 1: return i = partition(A, l, r) qs(A, l, i) qs(A, i + 1, r) def quicksort(A): return qs(A, 0, len(A))
QuickSort implementation from above does not behave well when there repeating elements.
Hoare Partitioning scheme fixes it:
HoarePartition($A$, $l$, $r$):
The QuickSort procedure stays the same
def hoare_partition(A, l, r): pi = pivot(A, l, r) p = A[pi] i = l j = r while True: while A[i] < p and i <= j: i = i + 1 while A[j] > p and j >= i: j = j - 1 if i >= j: return j A[i], A[j] = A[j], A[i] i = i + 1 j = j - 1 def qs(A, l, r): if l >= r: return q = hoare_partition(A, l, r) qs(A, l, q) qs(A, q + 1, r) def quicksort(A): return qs(A, 0, len(A) - 1)
Quickselect is an algorithm for computing $i$th order statistics
Problem
Reduction to sorting
modification for QuickSort:
how to find $i$th order?
RSelect(array $A$, len $n$, order $i$)
Best pivot - the median
def r_select(A, l, r, i): n = r - l if n == 0: return A[l] pi = partition(A, l, r) if i == pi: return A[pi] if pi < i: return r_select(A, pi + 1, r, i) else: return r_select(A, l, pi, i) def ith_order_statistic(A, i): return r_select(A.copy(), 0, len(A), i)
If there are repeating elements:
Solution:
def partial_quicksort(A, l, r, i): if l >= r: return q = hoare_partition(A, l, r) if i <= q: partial_quicksort(A, l, q, i) else: partial_quicksort(A, q + 1, r, i) def ith_order_statistic(A, i): A = A.copy() partial_quicksort(A, 0, len(A) - 1, i) return A[i]