Skip to main content

Sorting

Selection sort​

src/selection_sort.py
# Say we are given the following array to sort: 5 8 2 3 7 9
# Step 1: find the biggest element in first (n - 1) element and swap it with the
# last element if it is bigger than the last element else do nothing
# Step 2: find biggest element in first (n - 2) element, and swap it with
# (n-1)th element if it is bigger

def selection_sort(arr):
    # note that `arr` will be mutated and modified in-place, if you wat to
    # preserve, make deep copy by `arr_copy = arr.copy()` before modifying and
    # return modified array
    n = len(arr)
    for i in range(n - 1):
        biggest = max(arr[:(n - 1 - i)])
        id = arr.index(biggest)
        if biggest > arr[n - 1 - i]:
            arr[n - 1 - i], arr[id] = arr[id], arr[n - 1 - i]
        print("Step", i + 1, "=>", arr)


if __name__ == "__main__":
    arr = [5, 8, 2, 7, 6, 5]
    print("Un-order input:", arr)
    selection_sort(arr)
    print("Sorted output :", arr)

Insertion sort​

src/insertion_sort.py
# here we start sorting part of the array, then compare and insert next element
# so that the part with next element is sorted

def insertion_sort(arr):
    if len(arr) < 2:
        return

    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1
        print("Step", i, "=>", arr)


if __name__ == "__main__":
    arr = [5, 8, 2, 7, 6, 5]
    print("Un-order input:", arr)
    insertion_sort(arr)
    print("Sorted output :", arr)

Merge sort​

src/merge_sort.py
# recursively divide the array in two, sort each and merge them, much faster
# than selection and insertion sort, takes `n log(n)` time

def merge_sort(A, a = 0, b = None):
    if b is None:
        b = len(A)
    if 1 < b - a:
        c = (a + b + 1) // 2
        merge_sort(A, a, c)
        merge_sort(A, c, b)
        L, R = A[a:c], A[c:b]
        i, j = 0, 0
        while a < b:
            if (j >= len(R)) or (i < len(L) and L[i] < R[j]):
                A[a] = L[i]
                i += 1
            else:
                A[a] = R[j]
                j += 1
            a=a+1


if __name__ == "__main__":
    arr = [5, 8, 2, 7, 6, 5]
    print("Un-order input:", arr)
    merge_sort(arr)
    print("Sorted output :", arr)

Resources​