Module 1: Sorting I
Master basic sorting algorithms and their time complexities.
Learn how to implement and analyze sorting algorithms.
Sorting Fundamentals
Sorting is a fundamental operation in computer science that arranges elements in a specific order (typically ascending or descending). Efficient sorting is critical for many algorithms and applications.
Key sorting concepts include:
- Stability: Whether equal elements maintain their relative order
- In-place sorting: Algorithms that use O(1) extra space
- Comparison-based sorting: Algorithms that compare pairs of elements
- Time complexity: How runtime grows with input size
Bubble Sort Implementation
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.
// Bubble Sort Implementation
function bubbleSort(arr) {
const length = arr.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < length - 1; i++) {
if (arr[i] > arr[i + 1]) {
// Swap elements
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
} while (swapped);
return arr;
}
// Example usage
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]
Time Complexity:
- Best Case: O(n) - already sorted array with optimization
- Average Case: O(n²)
- Worst Case: O(n²)
Space Complexity: O(1) - in-place sorting
Insertion Sort Implementation
Insertion sort builds the final sorted array one item at a time, similar to sorting a hand of playing cards.
// Insertion Sort Implementation
function insertionSort(arr) {
const length = arr.length;
for (let i = 1; i < length; i++) {
// Store the current element
let current = arr[i];
let j = i - 1;
// Move elements that are greater than current
// to one position ahead of their current position
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
// Place current in its correct position
arr[j + 1] = current;
}
return arr;
}
// Example usage
const unsortedArray = [12, 11, 13, 5, 6];
console.log(insertionSort(unsortedArray)); // [5, 6, 11, 12, 13]
Time Complexity:
- Best Case: O(n) - already sorted array
- Average Case: O(n²)
- Worst Case: O(n²)
Space Complexity: O(1) - in-place sorting
Advantages of Insertion Sort:
- Simple implementation
- Efficient for small data sets
- Adaptive - runs faster on partially sorted arrays
- Stable sort - maintains relative order of equal elements
- Works well for nearly sorted data
Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing sorting algorithms.