Bubble Sort

• 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.