Sorting Algorithms

import math
l = [10, 1, 8, -3, 11, 114, 3]

Bubble Sort

1. With each pass we actually try to push largest element to the last position in the list.

2. In process we compare each element with the next element and swap the larger element to the right side.

def bubble_sort(l):
    length = len(l)
    for i in range(length):
        for j in range(0, length - i - 1):
            if l[j] > l[j+1]:
                temp = l[j]
                l[j] = l[j+1]
                l[j+1] = temp
            print(f"Pass : {i} | Comparing : {j} to {j+1} | {l}")

bubble_sort(l.copy())

Pass : 0 | Comparing : 0 to 1 | [1, 10, 8, -3, 11, 114, 3]
Pass : 0 | Comparing : 1 to 2 | [1, 8, 10, -3, 11, 114, 3]
Pass : 0 | Comparing : 2 to 3 | [1, 8, -3, 10, 11, 114, 3]
Pass : 0 | Comparing : 3 to 4 | [1, 8, -3, 10, 11, 114, 3]
Pass : 0 | Comparing : 4 to 5 | [1, 8, -3, 10, 11, 114, 3]
Pass : 0 | Comparing : 5 to 6 | [1, 8, -3, 10, 11, 3, 114]
Pass : 1 | Comparing : 0 to 1 | [1, 8, -3, 10, 11, 3, 114]
Pass : 1 | Comparing : 1 to 2 | [1, -3, 8, 10, 11, 3, 114]
Pass : 1 | Comparing : 2 to 3 | [1, -3, 8, 10, 11, 3, 114]
Pass : 1 | Comparing : 3 to 4 | [1, -3, 8, 10, 11, 3, 114]
Pass : 1 | Comparing : 4 to 5 | [1, -3, 8, 10, 3, 11, 114]
Pass : 2 | Comparing : 0 to 1 | [-3, 1, 8, 10, 3, 11, 114]
Pass : 2 | Comparing : 1 to 2 | [-3, 1, 8, 10, 3, 11, 114]
Pass : 2 | Comparing : 2 to 3 | [-3, 1, 8, 10, 3, 11, 114]
Pass : 2 | Comparing : 3 to 4 | [-3, 1, 8, 3, 10, 11, 114]
Pass : 3 | Comparing : 0 to 1 | [-3, 1, 8, 3, 10, 11, 114]
Pass : 3 | Comparing : 1 to 2 | [-3, 1, 8, 3, 10, 11, 114]
Pass : 3 | Comparing : 2 to 3 | [-3, 1, 3, 8, 10, 11, 114]
Pass : 4 | Comparing : 0 to 1 | [-3, 1, 3, 8, 10, 11, 114]
Pass : 4 | Comparing : 1 to 2 | [-3, 1, 3, 8, 10, 11, 114]
Pass : 5 | Comparing : 0 to 1 | [-3, 1, 3, 8, 10, 11, 114]

Selection Sort

1. First we find the smallest element and swap it with the first element. This way we get the smallest element at its correct position.

2. Then we find the smallest among remaining elements (or second smallest) and move it to its correct position by swapping.

3. We keep doing this until we get all elements moved to correct position.

def selection_sort(l):
    length = len(l)
    for i in range(length):

        min_val = math.inf
        idx = None
        for j in range(i, length):

            if l[j] < min_val:
                min_val = l[j]
                idx = j

        if idx:
            if l[i] > l[idx]:
                temp = l[idx]
                l[idx] = l[i]
                l[i] = temp

        print(f"Position : {i} | Min Element Idx: {idx} | {l}")
    return l


selection_sort(l.copy())

Position : 0 | Min Element Idx: 3 | [-3, 1, 8, 10, 11, 114, 3]
Position : 1 | Min Element Idx: 1 | [-3, 1, 8, 10, 11, 114, 3]
Position : 2 | Min Element Idx: 6 | [-3, 1, 3, 10, 11, 114, 8]
Position : 3 | Min Element Idx: 6 | [-3, 1, 3, 8, 11, 114, 10]
Position : 4 | Min Element Idx: 6 | [-3, 1, 3, 8, 10, 114, 11]
Position : 5 | Min Element Idx: 6 | [-3, 1, 3, 8, 10, 11, 114]
Position : 6 | Min Element Idx: 6 | [-3, 1, 3, 8, 10, 11, 114]

[-3, 1, 3, 8, 10, 11, 114]

def selection_sort(l):
    length = len(l)

    for i in range(0, length):
        for j in range(i + 1, length):
            if l[j] < l[i]:
                temp = l[j]
                l[j] = l[i]
                l[i] = temp
            print(f"Position : {i} | Comparing With Idx: {j} | {l}")
    return l

selection_sort(l.copy())

Position : 0 | Comparing With Idx: 1 | [1, 10, 8, -3, 11, 114, 3]
Position : 0 | Comparing With Idx: 2 | [1, 10, 8, -3, 11, 114, 3]
Position : 0 | Comparing With Idx: 3 | [-3, 10, 8, 1, 11, 114, 3]
Position : 0 | Comparing With Idx: 4 | [-3, 10, 8, 1, 11, 114, 3]
Position : 0 | Comparing With Idx: 5 | [-3, 10, 8, 1, 11, 114, 3]
Position : 0 | Comparing With Idx: 6 | [-3, 10, 8, 1, 11, 114, 3]
Position : 1 | Comparing With Idx: 2 | [-3, 8, 10, 1, 11, 114, 3]
Position : 1 | Comparing With Idx: 3 | [-3, 1, 10, 8, 11, 114, 3]
Position : 1 | Comparing With Idx: 4 | [-3, 1, 10, 8, 11, 114, 3]
Position : 1 | Comparing With Idx: 5 | [-3, 1, 10, 8, 11, 114, 3]
Position : 1 | Comparing With Idx: 6 | [-3, 1, 10, 8, 11, 114, 3]
Position : 2 | Comparing With Idx: 3 | [-3, 1, 8, 10, 11, 114, 3]
Position : 2 | Comparing With Idx: 4 | [-3, 1, 8, 10, 11, 114, 3]
Position : 2 | Comparing With Idx: 5 | [-3, 1, 8, 10, 11, 114, 3]
Position : 2 | Comparing With Idx: 6 | [-3, 1, 3, 10, 11, 114, 8]
Position : 3 | Comparing With Idx: 4 | [-3, 1, 3, 10, 11, 114, 8]
Position : 3 | Comparing With Idx: 5 | [-3, 1, 3, 10, 11, 114, 8]
Position : 3 | Comparing With Idx: 6 | [-3, 1, 3, 8, 11, 114, 10]
Position : 4 | Comparing With Idx: 5 | [-3, 1, 3, 8, 11, 114, 10]
Position : 4 | Comparing With Idx: 6 | [-3, 1, 3, 8, 10, 114, 11]
Position : 5 | Comparing With Idx: 6 | [-3, 1, 3, 8, 10, 11, 114]

[-3, 1, 3, 8, 10, 11, 114]

Insertion Sort

Merge Sort

Quick Sort