Overview
Sorting is the process of arranging a collection of data in a specific order (ascending or descending). Efficient sorting is fundamental to many other algorithms, such as Binary Search.
Core Concepts
- Stability: A sort is stable if it preserves the relative order of records with equal keys.
- In-Place: An algorithm is in-place if it requires a constant amount of extra space regardless of input size.
- Common Algorithms:
- Bubble Sort: Repeatedly swaps adjacent elements. $O(n^2)$. Simple but inefficient.
- Insertion Sort: Builds the sorted array one item at a time. $O(n^2)$. Efficient for nearly sorted data.
- Merge Sort: Divide-and-conquer. Splits array in half, sorts, and merges. $O(n \log n)$. Stable, but not in-place.
- Quick Sort: Picks a pivot and partitions the array. $O(n \log n)$ average, $O(n^2)$ worst case. In-place.
- Heap Sort: Uses a binary heap to sort. $O(n \log n)$. In-place.
Code Examples
// Simple Bubble Sort
function bubbleSort(arr: number[]) {
let n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}Use Cases
- Search Optimization: Data must be sorted before Binary Search can be used.
- Data Presentation: Sorting lists of users by name or products by price.
- Duplicate Removal: Sorting data makes identifying duplicates much faster.
Gotchas
- Choosing the Wrong Algorithm: Using Bubble Sort on a million records will freeze the application.
- Pivot Selection: In Quick Sort, picking a poor pivot (like the smallest element in a sorted array) leads to $O(n^2)$ performance.