Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
Quick Sort
#include <stdio.h>
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
int partition(int a[], int lo, int hi) { // Lomuto partition
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(&a[++i], &a[j]);
swap(&a[i + 1], &a[hi]);
return i + 1;
}
void quickSort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
}
int main() {
int a[] = {10, 7, 8, 9, 1, 5};
quickSort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
}1 5 7 8 9 10
Merge Sort
void merge(int a[], int l, int m, int r) {
int t[r - l + 1], i = l, j = m + 1, k = 0;
while (i <= m && j <= r) t[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= m) t[k++] = a[i++];
while (j <= r) t[k++] = a[j++];
for (k = 0; k < r - l + 1; k++) a[l + k] = t[k];
}
void mergeSort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}Track your progress through the Data Structures course