Basic Sorting Algorithms with Implementation in Python

Sorting is one of the most fundamental operations in computer science. Whether you are organizing a list of names, prices, or sensor timestamps from an IoT device, understanding how sorting works under the hood is crucial for writing efficient code.

In this post, we explore three classic sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort. While modern Python uses Timsort (a highly optimized hybrid algorithm), learning these basics helps build a strong intuition for algorithm complexity and trade-offs.

1. Bubble Sort

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. It is called "bubble" sort because the largest elements gradually "bubble up" to their correct positions at the end of the array.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. Selection Sort

Selection Sort maintains two sub-arrays: one already sorted and one remaining to be sorted. In every iteration, it finds the minimum element from the unsorted sub-array and moves it to the end of the sorted sub-array.

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3. Complexity Comparison

Algorithm	Best Case	Average Case	Worst Case	Space Complexity
Bubble	O(n)	O(n²)	O(n²)	O(1)
Selection	O(n²)	O(n²)	O(n²)	O(1)
Insertion	O(n)	O(n²)	O(n²)	O(1)

For the full implementation and more details, check out my original post on Medium.