Bubble Sort

EDIT (06/05/2014):

  • Code in this post is now available here as a single, executable file.

  • Added a section to this post containing code to test the bubble sort algorithm.


Here's my implementation of bubble sort in Go. This wasn't so much a whim as it was more just refreshing my algorithms knowledge.

I thought I was being slick by using slices to iterate through the number array, but it was somewhat confusing. I just would have liked to try something specific to Go instead of simple pointers. Formatted for readability. Anyways:

func bubbleSort(slice []int) {

  for end := (len(slice) - 1); end >= 0; end-- {

    for iteratingSlice := slice;    
    &iteratingSlice[0] != &slice[end];  
    iteratingSlice = iteratingSlice[1:] {

      if iteratingSlice[0] > iteratingSlice[1] {
        elementHolder := iteratingSlice[0]
        iteratingSlice[0] = iteratingSlice[1]
        iteratingSlice[1] = elementHolder
      } //Close if block

    } //Close inner for loop
  } //Close outer for loop
} //Closing function brace

Analysis

Outer for loop

for end := (len(slice) - 1); end >= 0; end-- {
    /* other code */
}

This for loop makes use of an integer variable end. End will initially refer to the last cell and move one cell at a time from right to left until it reaches the first cell.

The inner loop will need access to every element, starting at the first cell and `bubble` up the largest value to the right. Since the element at the end of each iteration is guaranteed to be sorted, the inner loop doesn't need to do anything with that element anymore. We make the inner loop ignore it by reducing end, thus shortening the length of the slice to kind of `hide` it.

Inner for loop

for iteratingSlice := slice;    
    &iteratingSlice[0] != &slice[end];  
    iteratingSlice = iteratingSlice[1:] {
    /* other code */
}    

iteratingSlice initially copies the header values from slice.

At each iteration, iteratingSlice is sliced to refer to a smaller portion of itself. The expression iteratingSlice[1:] refers to the second element of the slice to the end. This way, by "truncating" the first cell, we're slowly moving up the array from left to right. Remember that nothing is actually truncated, the slice as a whole is still intact, we're only changing the portion that iteratingSlice is referring to.

The loop exits when the address of the first cell of iteratingSlice is the equivalent to the address of the cell that end is currently referring to. This indicates that the iteration is completed.

If block

if iteratingSlice[0] > iteratingSlice[1] {
        elementHolder := iteratingSlice[0]
        iteratingSlice[0] = iteratingSlice[1]
        iteratingSlice[1] = elementHolder
      } //Close if block

This is probably the easiest part. We're only comparing two cells. If the value of the first cell is greater than the value of the second cell, swap them. We make use of a variable to temporarily hold a value as the cells are being swapped.

Testing the Algorithm

The following code was used to test the algorithm.

func main() {  
    numberSlice := []int{1, 4, 6, 8, 7, 9, 3, 5, 2}

    fmt.Printf("\nMain, unsorted integer array: %v\n", numberSlice)

    Sort(numberSlice)

    fmt.Printf("\nMain, sorted integer array: %v\n\n", numberSlice)
}

Output

Main, unsorted integer array: [1 4 6 8 7 9 3 5 2]

Main, sorted integer array: [1 2 3 4 5 6 7 8 9]  

Conclusion

Hope this was easy to follow, please feel free to make any suggestions or corrections. In further implementations I will attempt to provide tests. I also may decide to have each algorithm return a status to completment error handling...