Algorithm | WC | AC/E | Stable? |
---|---|---|---|
INSERTION-Sort | Θ(n^2) | Θ(n^2) | Yes |
MERGE-Sort | Θ(n lg n) | Θ(n lg n) | Yes |
Binary search | Θ(lg n) | Θ(lg n) | - |
Quicksort | Θ(n^2) | Θ(n lg n)* | Usually not*** |
Randomized-Quicksort | O(n lg n) | O(n lg n) | Usually not*** |
Counting-Sort | Θ(n+k) | Θ(n+k) | Yes |
Radix-Sort | Θ(d(n+k)) | Θ(d(n+k)) | Yes**** |
Bucket-Sort | Θ(n^2) | Θ(n)** | Yes |
Heap-Sort | O(n lg n) | O(n lg n) | No |
*Expected, Randomized-Quicksort
**Average-case
***Most quicksort implementations are not stable, though stable implementations do exist.
****LSD requires stability, MSD does not
Pseudocode
INSERTION-Sort(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j - 1].
i = j-1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key
Pseudocode
MERGE-Sort(A, p, r)
if p < r
q = ⌊(p + r)/2⌋
MERGE-Sort(A, p, q)
MERGE-Sort(A, q + 1, r)
MERGE(A, p, q, r)
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1..n1 + 1] and R[1..n2 + 1] be new array
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
Pseudocode
Bisect(A, p, r, v)
i = p
if p < r
q = ⌊(p + r)/2⌋
if v <= A[q]
i = Bisect(A, p, q, v)
else i = Bisect(A, q + 1, r, v)
return i
Pseudocode
Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1
Quicksort(A, p, r)
if p < r
q = Partition(A, p, r)
Quicksort(A, p, q - 1)
Quicksort(A, q + 1, r)
Pseudocode
Randomized-Partition(A, p, r)
i = Random(p, r)
exchange A[r] and A[i]
return Partition(A, p, r)
Randomized-Quicksort(A, p, r)
if p < r
q = Randomized-Partition(A, p, r)
Randomized-Quicksort(A, p, q - 1)
Randomized-Quicksort(A, q + 1, r)
Pseudocode
Counting-sort(A, B, k)
let C[0..k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]]+1
for i = 1 to k
C[i] = C[i] + C[i-1]
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
Pseudocode
Radix-Sort(A,d)
for i = 1 to d
sort* A by digit d
*Must be stable**
**Do not exchange equal values
Use: Counting-sort, Bucket-sort or Merge-sort
Pseudocode
Bucket-Sort(A)
n = A.length
create B[0 ..n - 1]
for i = 1 to n
make B[i] an empty list
for i = 1 to n
add A[i] to B[⌊nA[i]⌋]
for i = 0 to n - 1
sort list B[i]
concatenate B[0] ... B[n - 1]
Pseudocode
Heapsort(A)
Build-Max-Heap(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.size = A.size - 1
Max-Heapify(A, 1)
Build-Max-Heap(A)
A.size = A.length
for i = ⌊A.length/2⌋ downto 1
Max-Heapify(A, i)
Max-Heapify(A, i)
l = Left(i) // Left(i) = 2i
r = Right(i) // Right(i) = 2i + 1
if l <= A.size and A[l] > A[i]
m = l
else m = i
if r <= A.size and A[r] > A[m]
m = r
if m != i
exchange A[i] with A[m]
Max-Heapify(A, m)