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 (Java)
public static int[] bubbleSort(int[] arr) {
int length = arr.length;
boolean swapped;
do {
swapped = false;
for (int i = 0; i < length - 1; i++) { if (arr[i]> arr[i + 1]) {
// Swap elements
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
} while (swapped);
return arr;
}
// Example usage
public static void main(String[] args) {
int[] unsortedArray = {64, 34, 25, 12, 22, 11, 90};
System.out.println(Arrays.toString(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 (Java)
public static int[] insertionSort(int[] arr) {
int length = arr.length;
for (int i = 1; i < length; i++) { int current=arr[i]; int j=i - 1; while (j>= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
// Example usage
public static void main(String[] args) {
int[] unsortedArray = {12, 11, 13, 5, 6};
System.out.println(Arrays.toString(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.