Notes to Quiz

Maximilian

Intro

I recently took a data structures and algorithms course as part of my pursuit to learn lower level programming and computer science concepts. As the saying goes, the best way of solidifying your knowledge in something is to teach it, and since I've already filled my quota for boring my partner with coding talk for the month (probably the year), I thought I'd write a series of posts with some of the things I've learned. This is one such post.

What is the Bubble Sort Algorithm

The Bubble Sort algorithm is typically applied where simplicity is favoured over efficiency. It has a time complexity of O(n^2) which is less than ideal when dealing with larger lists.

How does it work

To explain how it works, here's some pseudo-code:

for pointer1 in list
    for pointer2 in list
        if list[j] > list[j + 1]
            swap list[j] and list[j + 1]
        pointer2++

    pointer1++

The idea of this algorithm is to 'bubble up' the larger items in the list to the end. We can think of this with 2 pointers, pointer1 and pointer2. We start by setting both pointers to the first item in the list. We then go through the entire list with pointer2 and swap the item at pointer2's position if the item at position pointer2 + 1 is greater in value. We keep repeating this process until we reach the end of the list. We then move pointer1 up by 1 and we start the process again with pointer2.

You may have noticed that we need a way of avoiding checking items that we have already sorted. Seeing as the aim of each iteration is to move the larger items to the end of the list, we can do this by limiting the boundary of pointer2 by the value of pointer1 + 1.

How do we implement it

Here's a heavily commented implementation in Typescript:

function bubbleSort(arr: number[]): void {
    // pointer 1
    for (let i = 0; i < arr.length; ++i) { 
       // pointer 2 + limit iterations by pointer1 + 1
        for (let j = 0; j < arr.length - 1 - i; ++j) {
            // check if current item is larger than the next item
            if (arr[j] > arr[j + 1]) {
                // temporarily store the current item so we don't lose it
                const tmp = arr[j];
                // swap the items in the array
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Sorted

This isn't a likely go-to algorithm in most cases, but I think it's a nice and easy one to get started. I hope you found it useful or, at least, a little bit interesting!