Loading...
Master fundamental algorithms for organizing and finding data
Section 1 of 5
Core concepts that underpin all sorting and searching algorithms
Before diving into specific algorithms, we need to understand the fundamental properties and concepts that differentiate them. These concepts help us choose the right algorithm for the right situation.
A sorting algorithm is stable if it preserves the relative order of equal elements.
Example:
Input: [(3,a), (1,b), (3,c), (2,d)]
Stable: [(1,b), (2,d), (3,a), (3,c)] ✓ (a before c)
Unstable: [(1,b), (2,d), (3,c), (3,a)] ✗ (c before a)
An in-place algorithm uses O(1) or O(log n) extra space (excluding input).
In-Place (O(1) space)
Not In-Place (O(n) space)
Comparison-Based
Decide order by comparing elements (a < b, a > b)
Lower bound: Ω(n log n)
Non-Comparison
Use other properties (digit, count, bucket)
Can achieve O(n) time!
An adaptive algorithm takes advantage of existing order in the input.
Example: Insertion Sort is O(n) on nearly-sorted data, but O(n²) on random data.
Non-adaptive algorithms (like Heap Sort) always perform the same operations regardless of input order.
| Complexity | Name | Examples | Use Case |
|---|---|---|---|
| O(n) | Linear | Counting Sort, Bucket Sort | Limited range integers |
| O(n log n) | Linearithmic | Merge Sort, Heap Sort, Quick Sort (avg) | General-purpose sorting |
| O(n²) | Quadratic | Bubble, Selection, Insertion Sort | Small datasets, nearly sorted |
| O(log n) | Logarithmic | Binary Search | Sorted data search |
For comparison-based sorting, we can prove that Ω(n log n) comparisons are required in the worst case.
Every comparison-based sorting algorithm can be represented as a decision tree:
n! permutations → tree needs n! leaves
Binary tree of height h has ≤ 2^h leaves
2^h ≥ n! → h ≥ log₂(n!) ≈ n log n
This means no comparison-based sorting algorithm can beat O(n log n) in the worst case!
Scenario:
You need to sort 1 million student records (name, grade, id) by grade. If two students have the same grade, their original order (by ID) should be preserved.
Best choice: Merge Sort