Bubble Sort

• Iterate through the array elements one by one, and check if one is greater than the other.
• If yes, swap the two elements
• After every run, it is guranteed that the last element will be sorted. We can slowly make the range smller by 1 element each time, hence j < len(slice)-i-1
• Optimized: If no elements were swapped after the first iteration, that means no element is out of order. We can stop sorting.

Complexities

Time Complexity

O(N) Best case - When elements are already sorted

O(N^2) On average - Total number of comparisons = n(n-1)/2

O(N^2) Worst case - When array is reversed sorted

Space Complexity

O(1)

Implementation

func bubbleSort(slice []int) {
	for i := 0; i < len(slice); i++ {
		for j := 0; j < len(slice)-i-1; j++ {
			if slice[j] > slice[j+1] {
				tmp := slice[j+1]
				slice[j+1] = slice[j]
				slice[j] = tmp
			}
		}
	}
}

func bubbleSortOptimized(slice []int) {
	swapped := false
	for i := 0; i < len(slice); i++ {
		for j := 0; j < len(slice)-i-1; j++ {
			if slice[j] > slice[j+1] {
				tmp := slice[j+1]
				slice[j+1] = slice[j]
				slice[j] = tmp
				swapped = true
			}
			if !swapped {
				break
			}
		}
	}
}

func main(){
    b := []int{33, 1, 5, 8, 22, 1, 55, 5, 99, 123, 90, 456, 333, 890, 1000, 999}
	fmt.Println("Before:", b)
	bubbleSort(b)
	fmt.Println("After:", b)

	c := []int{33, 1, 5, 8, 22, 1, 55, 5, 99, 123, 90, 456, 333, 890, 1000, 999}
	fmt.Println("Before:", c)
	bubbleSortOptimized(c)
	fmt.Println("After:", c)
}