3.9 Bubble Sort

1. Bubble Sort

A sorted array has no inversions, while an unsorted array has inversions. We only need to swap the inversions.

• Multiple passes
• Compare adjacent items in each pass; if they form an inversion, swap them

2. Characteristics

• Stability: stable
• Time complexity: O(n²)
• Space complexity: O(1)

3. Implementation

//O(N²)
func BubbleSort(data []model.Comparable) {
	for i := 0; i < len(data); i++ {
		for j := 0; j < len(data)-i-1; j++ {
			if data[j].CompareTo(data[j+1])>0 {
				util.Swap(data, j, j+1)
			}
		}
	}
}

3.1. Test

func TestBubbleSort(t *testing.T) {
	e0 := model.NewElement(0)
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)

	data := []model.Comparable{e2, e1, e3, e0, e4}
	fmt.Println(data)

	BubbleSort(data)
	fmt.Println(data)
}

4. Optimization

• If there is no swap in a pass, the array is already sorted, so exit directly

func BubbleSort2(data []model.Comparable) {
	for i := 0; i < len(data); i++ {
		ordered := true
		for j := 0; j < len(data)-i-1; j++ {
			if data[j].CompareTo(data[j+1]) > 0 {
				ordered = false
				util.Swap(data, j, j+1)
			}
		}
		if ordered {
			break
		}
	}
}

5. References

• Sorting Algorithm Stability - Baidu Baike