Bubble Sort – Go Program

Go – Bubble Sort

In this tutorial, we will learn how to implement the Bubble Sort algorithm in the Go programming language (Golang).

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted. We will provide a detailed explanation and example program to understand and implement Bubble Sort.

---

Logic of Bubble Sort

The Bubble Sort algorithm involves the following steps:

1. Outer Loop: Iterate through the list multiple times.
2. Inner Loop: Compare each pair of adjacent elements.
3. Swap Elements: If the first element is greater than the second, swap them.
4. Repeat: Continue the process until no swaps are needed, indicating that the list is sorted.
5. Optimization: Stop the algorithm early if no swaps are made in an iteration (indicating the list is already sorted).

Bubble Sort has a time complexity of \( O(n^2) \) for a list of size \( n \), making it less efficient for large datasets.

---

Go Program for Bubble Sort

Program – bubble_sort.go

package main

import "fmt"

// Function to implement Bubble Sort
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                // Swap elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }
        // If no swaps were made, the list is already sorted
        if !swapped {
            break
        }
    }
}

func main() {
    // Input array
    arr := []int{64, 34, 25, 12, 22, 11, 90}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Bubble Sort
    bubbleSort(arr)

    // Display the sorted array
    fmt.Println("Sorted array:", arr)
}

Explanation of Program

1. Function Definition: The bubbleSort function accepts a slice of integers and sorts it in ascending order using the Bubble Sort algorithm.
2. Outer Loop: The outer loop iterates through the array multiple times, reducing the range of elements to be checked in each iteration.
3. Inner Loop: The inner loop compares adjacent elements and swaps them if they are in the wrong order.
4. Swap Elements: Elements are swapped using the Go shorthand syntax arr[j], arr[j+1] = arr[j+1], arr[j].
5. Early Termination: The swapped variable tracks whether any swaps were made in an iteration. If no swaps are made, the loop terminates early, optimizing performance.
6. Display Results: The original and sorted arrays are printed to the console using fmt.Println.

Output

This program demonstrates the Bubble Sort algorithm and optimizes it with an early termination condition when no swaps are required in an iteration.