A stable quadratic sorting algorithms. [Best: O(n), Average: O(n²), Worst: O(n²), Space: O(1)]

Idea

The idea of the bubble sort is to iteratively step through the array, compare pairs of adjacent items and swap them if needed. The largest item will quickly “bubble” to the end during one iteration. In an optimized implementation, it only takes O(n) scans for an already sorted array of n items. However, the performance is very slow for average cases.

Implementation

Below is an optimized implementation of bubble sort in golang. Each iteration in outer loop will keep track of the large items those have been already in their final positions. So the next iteration will skip those items.

bubble_sort.gosource

package sorting

func BubbleSort(arr []int) {
	n := len(arr)
	for n > 0 {
		newn := 0
		for i := 1; i < n; i++ {
			if arr[i-1] > arr[i] {
				arr[i], arr[i-1] = arr[i-1], arr[i]
				newn = i
			}
		}
		n = newn
	}
}

References:

1. https://en.wikipedia.org/wiki/Bubble_sort
2. https://github.com/billjh/algo/tree/master/sorting

---

#algorithms #sorting #golang

Friday, Feb 17 2017