Key Sorting Algorithms Every Coder Should Know - 1

2 min read

🫧 1. Bubble Sort
Compare adjacent pairs of elements in an array and swap them if they are in the wrong order, gradually moving larger elements to the end of the array.
1.1. Time Complexity
Average / Worst case: O(n^2)
Best case: O(n) (already sorted)
1.2. Space Complexity
- O(1)
1.3. Code
def bubble_sort(l: List[int]) -> List[int]:
n = len(l)
for i in range(n-1):
for j in range(n-i-1):
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
📍2. Selection Sort
Find the minimum element from the unsorted portion of the array and swap it with the first unsorted element.
2.1. Time Complexity
- All cases: O(n^2)
2.2. Space Complexity
- O(1)
2.3. Code
def selection_sort(l: List[int]) -> List[int]:
n = len(l)
for i in range(n):
min_index = i
for j in range(i+1, n):
if l[min_index] > l[j]:
min_index = j
if m != i: # prevent unnecessary swap
l[i], l[m] = l[m], l[i]
🪛 3. Insertion Sort
Take each element from the unsorted portion and insert it into its correct position within the sorted portion of the array.
3.1. Time Complexity
Worst case: O(n^2)
Performs well for small or nearly sorted list.
3.2. Space Complexity
- O(1)
3.3. Code
def insertion_sort(l: List[int]) -> List[int]:
n = len(l)
for i in range(1, n):
j = i
while l[j-1] > l[j] and j > 0:
l[j-1], l[j] = l[j], l[j-1]
j -= 1
✨ Summary
Algorithm | Time Complexity (Worst) | Time Complexity (Best) | Space Complexity | Stable? |
Bubble Sort | O(n²) | O(n) | O(1) | Yes |
Selection Sort | O(n²) | O(n²) | O(1) | No |
Insertion Sort | O(n²) | O(n) | O(1) | Yes |
🔗 References
0
Subscribe to my newsletter
Read articles from EJ Jung directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
