Sorting Algorithms

4 minute read

Since I’m learning algorithms these days (cramming Leetcode actually), I find it quite necessary and interesting to do some notes about sorting algorithms, a series of common knowledge for every programmer.

I’ll be realizing these algorithms myself using Python, in order to put the process in practice for better familiarity.

And here is the GitHub repo for these algorithms.

Quicksort

""" self-realized quicksort python version """
# https://www.youtube.com/watch?v=COk73cpQbFQ


def partition(l: list, start: int, end: int, reverse: bool = False):
    # last element as pivot
    pivot = l[end]
    pIndex = start
    for i in range(start, end):
        if reverse:

            if l[i] >= pivot:
                # swap larger ones to left of the pIndex
                l[pIndex], l[i] = l[i], l[pIndex]
                pIndex += 1
        else:

            if l[i] <= pivot:
                # swap smaller ones to left of the pIndex
                l[pIndex], l[i] = l[i], l[pIndex]
                pIndex += 1
    # swap the pivot
    l[pIndex], l[end] = l[end], l[pIndex]
    return pIndex


def quicksort(l: list, start: int, end: int):

    if start >= end:
        return
    pIndex = partition(l, start, end)
    quicksort(l, start, pIndex-1)
    quicksort(l, pIndex+1, end)


c = [2, 1, 3, 4, 8, 10, 7, 6]
quicksort(c, 0, len(c)-1)
print(c)

Quicksort is a Divide and Conquer algorithm (just like Mergesort). It implements a technique called partition to sort everything. Partition basically uses a pivot (could be any index, I used the last index of every array), and put elements that are lesser to the left of it and larger to the right of it (during a ascending sort).

Then, it uses the [start, pivot_index - 1] and [pivot_index + 1, end] as the array to be sort into the recursive children functions. The algorithm uses index to identify the array and thus it is a in-place (does not create extra data structure to run the algorithm) algorithm.

It is also a non-stable algorithm (a sorting algorithm is said to be stable if it maintains the relative order of records in the case of equality of keys).

It’s time complexity is $O(nlogn)$

Big-O cheatsheet

Referenced from Towards Data Science



Mergesort

""" self-realized mergesort python version """
# https://www.youtube.com/watch?v=TzeBrDU-JaY&t=232s


def merge(a: list, b: list) -> list:
    merged = []
    ai, bi = 0, 0
    while ai < len(a) and bi < len(b):
        if a[ai] <= b[bi]:
            merged.append(a[ai])
            ai += 1
        else:
            merged.append(b[bi])
            bi += 1
            
    # put in the remaining elements
    for i in range(ai, len(a)):
        merged.append(a[i])
    for i in range(bi, len(b)):
        merged.append(b[i])

    return merged


def mergesort(l: list):
    mid = len(l) // 2
    
    # split in half
    a = l[:mid]
    b = l[mid:]
    if len(l) <= 2:
        return merge(a, b)
    
    # recursively merge two split arrays
    return merge(mergesort(a), mergesort(b))


c = [2, 4, 1, 6, 8, 5, 7, 7, 3, 7]
print(mergesort(c))

Mergesort is also a Divide and Conquer algorithm, much like the quicksort. It is more intuitive and closer to the divide and conquer nature: it splits the list in half recursively, and merge them back in ascending order.

The merge and sort are divided into two parts, much like the partition and sort in quicksort.

Mergesort is a stable sorting algorithm.
Mergesort’s time complexity: $O(nlogn)$


Insertion sort

""" self-realized insertion sort python version """
# https://www.youtube.com/watch?v=i-SKeOcBwko


def insertionsort(a: list):
    bound = 1
    while bound < len(a):
        curr, insert = a[bound], 0
        # iterate downward from the boundary between sorted and unsorted (bound)
        for j in range(bound-1, -1, -1):
            if a[j] >= curr:
                # move the cards
                a[j+1] = a[j]
            else:
                # found the insertion index
                insert = j + 1
                break
        a[insert] = curr
        bound += 1
    return a


l = [7, 2, 4, 1, 5, 3]
print(insertionsort(l))

Insertion sort sorts the numbers just like how we human sort cards. It has two parts: sorted and unsorted. And it moves the card from unsorted to sorted by comparing the current unsorted card with each card from the sorted pile, and decide the right index to insert it.

Time complexity: $O(n^2)$
Stability: True


Bubble sort

""" self-realized bubble sort python version """
# https://www.youtube.com/watch?v=Jdtq5uKz-w4


def bubblesort(a: list):
    length = len(a)
    for i in range(length):
        flag = 0
        for j in range(length - i - 1):
            # no need to go through the sorted part
            if a[j] >= a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                flag = 1
        if flag == 0:
            # no swap at all: already sorted
            break
    return a


l = [2, 3, 1, 4, 7, 5]
print(bubblesort(l))

Bubble sort’s princple is quite straight-foward, it swaps each element with the element right next to it to “bubble up” the larger ones to the right of the array. And it does this process n times to make sure the whole array is sorted.

Time complexity: $O(n^2)$
Stability: True


Selection sort

""" self-realized selection sort python version """
# https://www.youtube.com/watch?v=GUDLRan2DWM


def find_min_index(a: list, start: int) -> int:
    min_ = float('inf')
    min_i = 0
    for i in range(start, len(a)):
        if a[i] <= min_:
            min_ = a[i]
            min_i = i
    return min_i


def selectionsort(a: list) -> list:
    count = 0

    while count < len(a):
        min_i = find_min_index(a, count)
        a[count], a[min_i] = a[min_i], a[count]
        count += 1

    return a


print(selectionsort([2, 3, 1, 4, 7, 5]))

Selection sort turns out to be the easiest sorting algorithm among these ones. Its logic cannot get simpler, it finds the minimum element from the unsorted pile and put the element into the sorted pile. And it repeats this process n times. It is intuitive and I think there are many of us sort cards using this idea.

Time complexity: $O(n^2)$
Stability: False

Tags:

Categories:

Updated: