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
def bubble_sort(arr):
length = len(arr)
swapped = True
while swapped:
swapped = False
for i in range(length - 1):
if arr[i] > arr[i + 1]:
# Swap elements
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
return arr
# Example usage
unsorted_array = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(unsorted_array)) # [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
def insertion_sort(arr):
length = len(arr)
for i in range(1, length):
current = arr[i]
j = i - 1
# Move elements that are greater than current
# to one position ahead of their current position
while j >= 0 and arr[j] > current:
arr[j + 1] = arr[j]
j -= 1
# Place current in its correct position
arr[j + 1] = current
return arr
# Example usage
unsorted_array = [12, 11, 13, 5, 6]
print(insertion_sort(unsorted_array)) # [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.