Bubble sort in Go

Key takeaways:
Bubble sort follows a comparative approach, iterating over the list and swapping out-of-order elements.
It has a time complexity of $O(n²)$ , making it less efficient for large datasets.
Go is a great language to implement sorting algorithms due to its simplicity and performance characteristics.

Bubble sort compares adjacent elements and swaps them if they are in the wrong order repeatedly throughout the array. It continues until the entire array is sorted, ensuring that larger elements are at the end of the array.

Bubble sort is a very simple algorithm designed to compare adjacent elements in a list and swap them if they are not in the correct order. Although it’s not the most efficient sorting method, it’s an excellent algorithm for beginners to grasp fundamental sorting concepts.

Understanding the concept

For a better understanding of the concept of how bubble sort works, an illustration is displayed. In this illustration, the given list, i.e., $[5, 2, 4, 6, 1, 3]$ , is unordered. The bubble sort algorithm is applied to sort the list.

package main
import "fmt"
func bubbleSort(arr []int) {
	n := len(arr)
	swapped := true
	m := 0
	for swapped {
		swapped = false
		
		fmt.Println("iteration number: " ,m)
		for i := 1; i < n; i++ {
			if arr[i-1] > arr[i] {
				// Swap elements if they are in the wrong order
				arr[i-1], arr[i] = arr[i], arr[i-1]
				swapped = true
				
				
				
			}
		}
		n-- // The largest element is now in its correct position, so reduce the length of the unsorted part of the array
		
		fmt.Println("Sorted array:", arr)
		m++
	}
}
func main() {
	arr := []int{5, 2, 4, 6, 1, 3}
	fmt.Println("Unsorted array:", arr)
	bubbleSort(arr)
	fmt.Println("The sorted array is:", arr)
}

Code explanation

Line 5–29: The bubbleSort function takes an integer slice as input and sorts it in ascending order using the bubble sort algorithm.
Line 10–28: The outer loop (for swapped) runs until there are no more swaps in one pass, which indicates that the array is sorted.
Line 14–23: The inner loop (for i) compares adjacent elements and swaps them if necessary.

The array is successfully sorted in ascending order using the bubble sort algorithm. Remember that bubble sort is not the most efficient sorting algorithm and has a time complexity of $O(n^2)$ The space complexity of bubble sort is $O(1)$ . For larger datasets, more efficient sorting algorithms like merge sort or quick sort are preferred.

To further enhance your knowledge and skills in coding interviews, we recommend a specially designed path, Educative 99. This path offers interactive lessons that give hands-on experience with coding problems and opportunities to test and refine your solutions.

Time complexity

The time complexity of the algorithm is $O(n²)$ because every element needs to be compared with every other element. This makes it inefficient for large datasets.

Space complexity

Its space complexity is $O(1)$ because it sorts the array in place and only requires a few extra variables for tracking iterations and swaps.

Understanding these algorithms and patterns can be a game changer if you’re prepping for technical interviews. For LeetCode pattern-based problems, check out our course on "Coding Interview Patterns."

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How efficient is bubble sort?

Bubble sort has a time complexity of $O(n²)$ , making it inefficient for large datasets but useful for small or nearly sorted lists.

What is the best case time complexity of bubble sort?

The best case time complexity of bubble sort is $O(n)$ , which happens when the array is already sorted.

Is bubble sort stable?

Yes, bubble sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements.

What is bubble sort’s space complexity?

Bubble sort has a space complexity of $O(1)$ because it only uses a constant amount of extra memory.

Free Resources