Week 15 of 43
Core DSA
WEEK 15 LEARNING MODULE
Elementary Sorting Algorithms
Examines foundational comparison-based sorts (Bubble, Selection, Insertion) and non-comparison Counting Sort, analyzing stability, in-place memory, and Big-O bounds.
3 Practice Problems5 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Understand sorting classifications: comparison vs. non-comparison, stability, and in-place memory.
- ✓Implement Bubble Sort, Selection Sort, and Insertion Sort from first principles.
- ✓Implement Counting Sort in $O(n + k)$ linear time for bounded integer domains.
- ✓Apply sorting mechanics to solve Dutch National Flag (Sort Colors) and rank-reduction problems.
Core Concepts
Sorting Stability
Preserving the relative order of duplicate elements in the sorted output.
Bubble Sort
O(n²)Repeatedly stepping through list, swapping adjacent out-of-order elements.
Selection Sort
O(n²)Finding minimum element from unsorted portion and swapping to sorted prefix.
Insertion Sort
O(n²)Building sorted array one element at a time by inserting into correct position.
Counting Sort
O(n + k)Non-comparison sorting that counts key occurrences to place elements directly.
Algorithms Covered
Bubble SortSelection SortInsertion SortCounting SortDutch National Flag (3-Way Partition)
Data Structures Applied
Arrays
“In the short term, you are as good as your intensity. In the long term you are only as good as your consistency.”
— Shane Parrish