CLRS Chapters 6-9
Watch Heapsort, Quicksort, Counting Sort, and Quickselect come to life step-by-step.
Chapter 6
Build a max-heap, then repeatedly swap the root with the last element and heapify the reduced heap.
// Max-Heapify
void maxHeapify(A, i, n) {
largest = i;
l = 2*i + 1; r = 2*i + 2;
if (l < n && A[l] > A[largest]) largest = l;
if (r < n && A[r] > A[largest]) largest = r;
if (largest != i) {
swap(A[i], A[largest]);
maxHeapify(A, largest, n);
}
}
Chapter 7
Choose a pivot, partition the array so smaller elements are on the left and larger on the right, then recurse.
// Lomuto Partition
int partition(A, low, high) {
pivot = A[high];
i = low - 1;
for (j = low; j < high; j++) {
if (A[j] <= pivot) {
i++; swap(A[i], A[j]);
}
}
swap(A[i+1], A[high]);
return i + 1;
}
Chapter 8
No comparisons. Count frequencies, compute prefix sums, and place elements directly into their sorted positions.
Input Array
Count Array (Frequencies)
Output Array
void countingSort(A, n, k) {
count = new Array(k+1).fill(0);
for (i = 0; i < n; i++) count[A[i]]++;
for (i = 1; i <= k; i++) count[i] += count[i-1];
output = new Array(n);
for (i = n-1; i >= 0; i--) {
output[count[A[i]] - 1] = A[i];
count[A[i]]--;
}
}
Chapter 9
Find the k-th smallest element in linear time on average. Similar to Quicksort, but we only recurse into one side.
// Quickselect
int quickSelect(A, low, high, k) {
if (low == high) return A[low];
pivotIndex = partition(A, low, high);
count = pivotIndex - low + 1;
if (k == count) return A[pivotIndex];
else if (k < count)
return quickSelect(A, low, pivotIndex-1, k);
else
return quickSelect(A, pivotIndex+1, high, k-count);
}