Line 238: | Line 238: | ||
return r_select(A.copy(), 0, len(A), i) | return r_select(A.copy(), 0, len(A), i) | ||
− | If there are repeating elements, | + | If there are repeating elements, use HoarePartition instead: |
+ | |||
+ | def hoare_r_select(A, l, r, i): | ||
+ | n = r - l | ||
+ | if n == 0: | ||
+ | return A[l] | ||
+ | |||
+ | pi = hoare_partition(A, l, r) | ||
+ | if i == pi: | ||
+ | return A[pi] | ||
+ | if pi < i: | ||
+ | return hoare_r_select(A, pi + 1, r, i) | ||
+ | else: | ||
+ | return hoare_r_select(A, l, pi, i) | ||
+ | |||
+ | def ith_order_statistic(A, i): | ||
+ | return hoare_r_select(A.copy(), 0, len(A) - 1, i) | ||
== See also == | == See also == |
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: i = i + 1 while A[j] > p: 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)
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, use HoarePartition instead:
def hoare_r_select(A, l, r, i): n = r - l if n == 0: return A[l] pi = hoare_partition(A, l, r) if i == pi: return A[pi] if pi < i: return hoare_r_select(A, pi + 1, r, i) else: return hoare_r_select(A, l, pi, i) def ith_order_statistic(A, i): return hoare_r_select(A.copy(), 0, len(A) - 1, i)