Part 1 - Sorting

My other course for this study period is a course in Data Structures & Algorithms.

Sorting & Searching

We began this course with sorting and why it’s an important topic for a computer scientist. Sorting data comes up in all fields of computer science, everything from low-level, simple, array sorting - to sort millions of data gathered by an AI.

With this we began with simple sorting and searching algorithms. Firstly we began with binary search. Binary search is a simple yet powerful search algorithm for finding a value in a sorted array.

Pseudo Code for a Binary Search:

1
func binary_search(array, search_value):
2
    low  = first index of array
3
    high = last index of array
4

5
    # If our low and high pointers ever cross, we know that the element is not in the array
6
    while low <= high:
7
        mid  = mid index of array; (low + high) / 2
8

9
        if(search_value is to the left of mid value):
10
            continue search to the left of the array
11

12
        else if(search_value is to the right of mid value):
13
            continue search to the right of the array
14

15
        else:
16
            return mid
17

18
    return Not in array

And an actual Python implementation:

1
def binary_search(arr, val):
2
    low  = 0
3
    high = len(arr) - 1
4

5
    while low <= high:
6
        mid = (low + high) // 2
7

8
        if(val < arr[mid]):
9
            high = mid - 1
10

11
        elif(val > arr[mid]):
12
            low = mid + 1
13

14
        else:
15
            return mid
16
    return -1

The next step was Selection and Insertion sort, simple naive sorting algorithms.

The selection sort algorithm is: Find the smallest element in the list and swap it to the first index, then continue for the next-smallest etc.

An implementation:

1
def selection_sort(arr):
2
    size = len(arr)
3
    for index in range(size):
4
        min_index = index
5
        for j in range(index + 1, size):
6
            if(arr[j] < arr[min_index]):
7
                min_index = j
8
        (arr[index], arr[min_index]) = (arr[min_index], arr[index])

After that it was time for insertion sort, which builds on the idea of inserting a value in an array. The idea is that we start by saying that the first element is the ‘sorted’ part. Then we begin looking at the ‘unsorted’ part, at seeing where it should be inserted into the sorted array. A simple, yet, powerful algorithm. We will see how important the idea of inserting will be later on.

An implementation:

1
def insertion_sort(arr):
2
    # Begin by saying the first element is sorted
3
    # We call the
4
    for i in range(1, len(arr)):
5
        val = arr[i]
6

7
        j = i - 1
8
        while j >= 0 and val < arr[j]:
9
            arr[j + 1] = arr[j]
10
            j -= 1
11
        arr[j+ 1] = val

Although these algorithms are simple, they are unfortunately really slow, when the array becomes larges. For now, we can just say that why this is because: The number of operations needed to check and sort grows quadratic with the array size.

Imagine we have two sorted lists, and we want to merge them - what’s the algorithm for this? Quite simple actually, we use two pointers for knowing where we are in both arrays, starting at the first index and both and compare which value we insert into the new (bigger) array). Then we move the pointers accordingly, until we reach the end. Reaching the end here means we either hit the end of the array of both arrays simultaneously, or reaching the end of one array - if we do that we know there’s nothing left to compare to, therefore we can just put the rest of the elements in.

An implementation of a merge function:

1
def merge(arr1, arr2):
2
    # We can cheat a little bit using python - but the idea is still the same
3
    output = []
4
    p1     = 0
5
    p2     = 0
6

7
    while p1 < len(arr1) and p2 < len(arr2):
8
        if(arr1[p1] <= arr2[p2]):
9
            output.append(arr1[p1])
10
            p1 += 1
11
        else:
12
            output.append(arr2[p2])
13
            p2 += 1
14

15
    while p1 < len(arr1):
16
        output.append(arr1[p1])
17
        p1 += 1
18

19
    while p2 < len(arr2):
20
        output.append(arr2[p2])
21
        p2 += 1
22

23
    return output

Now that we’re familiar with this algorithm - we can use this by divide and conquering an unsorted array with a bit of modifications. We can imagine that we divide the unsorted array into a left and right part and recursively mergesort() them as well.

In practice, it means that we get a sorted left array and a sorted right array, then we finally merge them for the final result.

An implementation of merge sort:

1
def merge_sort(arr: list) -> list:
2
    if len(arr) < 2:
3
        return arr[:]
4
    else:
5
        mid = len(arr) // 2
6

7
        L = merge_sort(arr[:mid])
8
        R = merge_sort(arr[mid:])
9

10
  result = merge(L, R)
11
        return result

Merge sort is great, but sometimes, if the list is almost sorted or worse, already sorted and, you call this function sort it - it will be incredibly slow, this is due to merge sort not being a so called in place algorithm. An algorithm which has the same divide and conquer strategy but is in-place is Quicksort!

Quicksort builds on the idea that you partition your array into one part which is lower than the pivot element and one part which is higher.

In practice this means you sort it by recursively partitioning the sub-arrays.

So partitioning, sounds quite easy right? Choose a pivot element and just put larger numbers to the right and lower to the left. But choosing the pivot is the tricky part. If we choose a good pivot our algorithm becomes much faster. A common (and good) strategy is either choosing a random pivot, or the median of three.

In this example I will choose the pivot element as the last element of the list. An implementation of Quicksort:

1
def partition(arr, low, high):
2

3
    def swap(i, j):
4
        arr[i], arr[j] = arr[j], arr[i]
5

6
    pivot = arr[high]
7

8
    i = low - 1
9

10
    for j in range(low, high):
11
        if arr[j] <= pivot:
12
            i += 1
13
            swap(i, j)
14

15
    swap(i + 1, high)
16
    return i + 1
17

18
def quick_sort(arr, low, high):
19
    if low < high:
20

21
        p = partition(arr, low, high)
22

23
        quick_sort(arr, low, p - 1)
24

25
        quick_sort(arr, p + 1, high)

This concludes this part, next time I’ll write about (short) about Complexity - after that the major part of this course, actual data structures and how we use them as well as implement them.