Key Sorting Algorithms Every Coder Should Know - 1

EJ JungEJ Jung
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

AlgorithmTime Complexity (Worst)Time Complexity (Best)Space ComplexityStable?
Bubble SortO(n²)O(n)O(1)Yes
Selection SortO(n²)O(n²)O(1)No
Insertion SortO(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

EJ Jung
EJ Jung