Data Structures and Algorithms

Welcome!

The following is detailed information on the implementation of data structures and algorithms I have implemented. Perfect content for a “modern blog” format to casually enjoy and read.

I’ll be honest now. I’m trying to learn these topics, and I have a problem of solving these things and then coming back later totally lost on where to start. So this post is for me, to come back later and remember what I did before.

So, feel free to peruse. If you feel lost, or maybe you think the way I am doing it is confusing, then you should probably implement it yourself, create your own blog and write about it. Then it’ll make sense. 😂

Anyway, The problems are solved in golang, using a generic type T. More (and Less) are used as comparators of generic types, which currently has numeric and string types implemented.

What does that mean? Well, what is T < T? If T is a number, then it would be 1 < 2, if it’s a string, it would be “a” < “b”.

In the text, (n) is used to reference the group in the code blocks. It can reference multiple lines (in this case, the 2nd and 3rd line)

# Previous code
msg = "Hello World"
print("Hello World")
# Later code

I dislike looking at large blocks of code and having some blog say “See look at this 20 lines of code, it addresses problem X”. So while this is better (for me), please feel free to be confused and annoyed at my presentation style. Once I find the right way, I’ll use that instead.

Bubble Sort

K	V
Big O	O(n^2)
Space	O(1)

Good for almost already sorted arrays

(1) is used to track whether a sorting occurred. If it doesn’t, it’s done.

(2) means we should swap the items in the array. This is the sorting or bubbling up. We don’t use extra space because of this.

Finally, (3) shows once an item is sorted, we don’t need to consider it further. So while it is n^2 in runtime, it decreases by 1 each time.

func (arr *Array[T]) BubbleSort() {
  sorted := true
  sortedCount := 0
  for sorted {
    sorted = false
    for i := 0; i < len(*arr)-1-sortedCount; i++ {
      if More((*arr)[i], (*arr)[i+1]) {
        (*arr)[i], (*arr)[i+1] = (*arr)[i+1], (*arr)[i]
        sorted = true
      }
    }
    sortedCount++
  }
}

Let’s say you have an array of 5, 1, 2, 3, 4 A bubble sort will start from the left and compare 5 and 1. 1 is less than 5, so now it’s 1, 5, 2, 3, 4. We do it again with the next one. Since it’s 5 and it’s bigger then 2, 5 is moved up again! In this way, the 5 “bubbles” up to the end. We also know, because of this, that the last one is now “sorted”, so we can ignore it. On the next iteration, we will sort the next 4 elements, instead of all 5 again. So, this algorithm is O(n^2). Note that each iteration is problem size N-1.

Selection Sort

K	V
Big O	O(n^2)
Space	0(1)

Example

5, 9, 2, 2, 7

This keeps track of the smallest number at the start. So at index 0, it’s 5, right? 9 is bigger, so 5 is still the biggest value. Next one, 2 is smaller, so now the smallest is 2. Great. Repeat, Repeat, 2 is still the smallest at the end of our iteration. So now we switch 5 <-> 2. We know that index 0 is now the smallest value. So we start from index 1 now. Repeat until done.

Insertion Sort

K	V
Big O	O(n^2)
Space	O(1)

How this works is it takes the existing sorted ones and inserts between where it would fit. So 1, 3 <- 2 would have 2 inserted like 1, 2, 3. The nice thing is it does this in one pass, but during that pass it has to keep looping back. Making this O(n^2).

Notice where we make a copy by value (1) for use later. Also (2) notice how we keep track where to insert it.

func (arr *Array[T]) InsertionSort() {
  var extractedV T
  var p2 int
  for j := 1; j < len(*arr); j++ {
    extractedV = (*arr)[j]
    p2 = j
    for i := j; i > 0; i-- {
      if Less(extractedV, (*arr)[i-1]) {
        (*arr)[i] = (*arr)[i-1]
        p2--
      }
    }
    (*arr)[p2] = extractedV
  }
}

MergeSort

K	V
Big O	O(log(n))
Space	O(n)

We need to recursively do the following:

Split array in 2.
Have a struct with 3 values. The original array, the left side of the array and right side of the array.
Repeat until the array is size of 1.

Then,

Loop through the top structure, accessing the right side until size is just 1?

Here is the code in full. The first part (1) is the split, while the second part (2) is the merge. Also notice the edge cases. If p1 or p2 has reached the end, we use the other one and increment it.

func (arr *Array[T]) MergeSort() {
  var node Node[Array[T]]
  node.value = *arr

  var merge func(node *Node[Array[T]])
  merge = func(node *Node[Array[T]]) {
    l := node.left.value
    r := node.right.value

    pl, pr := 0, 0

    for i := 0; i < len(node.value); i++ {
      if pl == len(l) {
        node.value[i] = r[pr]
        pr++
        continue
      } else if pr == len(r) {
        node.value[i] = l[pl]
        pl++
        continue
      }
      if Less(l[pl], r[pr]) {
        node.value[i] = l[pl]
        pl++
      } else {
        node.value[i] = r[pr]
        pr++
      }
    }
  }

  var recursiveSplit func(node *Node[Array[T]])
  recursiveSplit = func(node *Node[Array[T]]) {
    l := len(node.value)
    m := l / 2
    if l > 1 {
      var lSide Node[Array[T]]
      var rSide Node[Array[T]]
      lSide.value = make(Array[T], len(node.value[:m]))
      rSide.value = make(Array[T], len(node.value[m:]))

      copy(lSide.value, node.value[:m])
      copy(rSide.value, node.value[m:])

      node.left = &lSide
      node.right = &rSide

      recursiveSplit(&lSide)
      recursiveSplit(&rSide)

      merge(node)
    }
  }

  recursiveSplit(&node)
}

To figure this out, we need to understand a few things:

We cannot merge until the sub arrays are sorted.
While merging, the current node’s value is not important (we may overwrite it)
merge(node) (3) will not run until the children have been merged, so we can trust it is sorted.

A stumbling block I had was to split everything, and then merge everything. This was a mistake. Instead, we merge right after we call recursiveSplit and the left and right side (3). This allows us to keep track of where we are. Originally, I had code trying to identify how to keep state, which I later realized I was throwing away by completing the full split before attempting the merge.

A realization I had is during recursion, you should always trust that whatever recursive function you called will be done by the time the next statement runs. It’s tricky to mentally wrap my mind around recursion, and this helped clarify it for me.

Bro Code - Learn Merge Sort in 13 minutes

Quicksort

K	V
Big O	O(log(n)) <-> O(n^2)
Space	O(1)

This is a shortcut that effectively says, “swap p1 with p2”
Exit the recursive function once the array length is 1

It is important to understand the foot-gun here. We are modifying the array (3), not creating new ones. So while the variables left and right look like new arrays, they are not. Modifying them modifies the top level array. This is why space is O(1).

func (arr *Array[T]) QuickSort() {
    var s func(a *Array[T])
    s = func(a *Array[T]) {
        if len(*a) < 2 {
            return
    }
    p1 := -1
    p2 := 0
    pivot := (*a)[len(*a)-1]

    for p2 < len(*a)-1 {
        if Less((*a)[p2], pivot) {
            p1++
            (*a)[p1], (*a)[p2] = (*a)[p2], (*a)[p1]
        }
        p2++
    }
    p1++
    (*a)[p1], (*a)[p2] = (*a)[p2], (*a)[p1]

    left := (*a)[:p1]
    right := (*a)[p1+1:]
    if len(left) > 1 {
        s(&left)
    }
    if len(right) > 1 {
        s(&right)
    }
}
  s(arr)
}

Bro Code - Learn Quick Sort in 13 minutes

Radix Sort

K	V
Big O	O(kn)
Space	O(n + b)

Works best with the numbers are around the same value (for example: 0-1_000_000)

Table of Contents