[CS Fundamentals] Sorting Algorithms

---

Selection Sort

Selection sort is the simplest way to sort an array.

Pretend that index 0 is the smallest, and we look at each element. We select the smallest element from other index and swap the two elements.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i

    for j in range(i + 1, len(array)):
        if array(min_index) > array[j]:
            min_index = j
        array[i], array[min_index] = array[min_index], array[i]

Time complexity: O(N²)

---

Insertion Sort

Insertion Sort is a bit more efficient than selection sort, and it works fast when array is somewhat sorted already.

Pretend that the first element (i.e. index 0) is already sorted.

For example, you have a list like this: array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]. The idea of insertion sort is that 5 is already sorted. Now, what we are going to do is looking at each element starting from index 0, we decide where the element should be placed.

We look at the next element, which is 7. 7 is greater than 5, so it remains at the same index.

9 is greater than 5 and 7, so it remains.

0 is smaller than 5, it moves to index 0.

3 is greater than 0, but smaller than 5, so it moves to index 1.

It goes on and on, then we get the sorted array!

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break

Time complexity: O(N²)

---

Quick Sort

Quick sort is the most efficient sorting alogrithm along with merge sort. Many programming language’s sorting libraries use quick sort.

In the quick sort algorithm, we have a pivot, and it is the first element.

The idea of it is that you find the element that is smaller than the pivot from the end of an array, and the element that is greater than the pivot from pivot + 1 index of an array.

So, let’s say left = pivot + 1, right = len(array) - 1. when left > right, you swap the pivot and right. Then do the same thing again.

This is the same as dividing the array by two, so it is efficient. To help you understand, have a look at this image:

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

Time complexity: O(NlogN)

The worst case scenario: O(N²)

The worst case is when an array is already sorted. For example, you have array = [1, 2, 3, 4, 5, 6, 7, 8] The computer is not like a human. It doesn’t know that this array is already sorted, so it does the quick sort. 1 is the pivot, and also the smallest value in the array. This means that it splits into two arrays like this: [1] and [2, 3, 4, 5, 6, 7, 8]. The number of dividing = N, and searching smaller and greater numbers than pivot also equals to N. So it is O(N²).

---

Counting Sort

Counting sort works very fast in certain circumstances, and it can be used

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

Even in the worst case: O(N + K)

But let’s say that we have array = [0, 9999999]. This is going to be so inefficient because we need to create an array with 9999999 elements to sort an array with a length of 2.

To maximize the advantage of counting sort algorithm, we can use it for sorting grade as the grade scales from 0 to 100.

---

Summary