Sorting
Sorting is the process of rearranging a set of data in a specific order, and is one of the most fundamental and most deeply studied algorithmic problems in data processing.
Sorting Algorithm Family
Basic Sorting (O(n²))
Bubble sort, selection sort, and insertion sort are simple to implement and suitable for small-scale data or teaching understanding.
Advanced Sorting (O(n log n))
Quicksort, merge sort, and heap sort are the most widely used in engineering. Shell sort is an improvement on insertion sort.
Examples
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Bubble sort — O(n²), stable
Each round "bubbles" the largest element to the end */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* Optimization: early termination */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* Already sorted, terminate early */
}
}
/* Quicksort partition function — O(n log n) average, unstable
Choose pivot; elements less than pivot go to the left, greater go to the right */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Choose the last element as pivot */
int i = low - 1; /* i points to the end of the region less than pivot */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* Place pivot in its correct position */
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); /* Partition index */
quickSort(arr, low, pi - 1); /* Recursively sort the left half */
quickSort(arr, pi + 1, high); /* Recursively sort the right half */
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("Bubble sort: "); printArray(arr1, n1);
/* Output: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("Quicksort: "); printArray(arr2, 7);
/* Output: 11 12 22 25 34 64 90 */
return 0;
}
Illustration of Divide and Conquer Concept
Quicksort (Partition)
Choose pivot
Less than pivot → left side, greater → right side
Recursively sort left and right subarrays
Unstable | In-place | Most commonly used
Merge Sort (Merge)
Recursively halve to the smallest unit
Merge two ordered subsequences
Requires extra array O(n)
Stable | Requires extra space | External sorting
Heap Sort (Heapify)
Build max heap O(n)
Place heap top (max) at the end
Re-adjust heap O(log n)
Unstable | In-place O(1) | Space-optimal
Complete Comparison of Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stability |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Stable |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Unstable |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Stable |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Unstable |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable |
| Shell sort | O(n log n) | O(n^1.3) | O(n²) | O(1) | Unstable |
Other ExtensionsPractical selection advice: for general scenarios, quicksort is the first choice; choose merge sort when stability is needed; choose heap sort when memory is extremely constrained; choose insertion sort for small-scale or nearly sorted data.