Key Sorting Algorithms Every Coder Should Know - 1

🫧 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

🔗 References

• Sorting Algorithms Explained in 10 min

• Comparison among Bubble Sort, Selection Sort and Insertion Sort