Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Go Implementation

package main

import (
    "fmt"
)

// bubbleSort function sorts an array of integers using the bubble sort algorithm.
func bubbleSort(arr []int) []int {
    n := len(arr)
    // Traverse through all elements in the array
    for i := 0; i < n-1; i++ {
        // Last i elements are already in place
        for j := 0; j < n-i-1; j++ { // Swap if the element found is greater than the next element if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

// main function is the entry point of the program
func main() {
    // Sample array to be sorted
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    sortedArr := bubbleSort(arr)
    fmt.Println("Sorted array:", sortedArr)
}
    

Program Structure

• Package Declaration: The program starts with the package declaration package main which defines the package name.
• Import Statement: We import the fmt package to facilitate input and output operations.
• bubbleSort Function: This function takes a slice of integers as input and sorts it using the bubble sort algorithm. It iterates through the array, comparing adjacent elements and swapping them if necessary.
• Main Function: The entry point of the program where we define an unsorted array, call the bubbleSort function, and print both the unsorted and sorted arrays.

Documentation

The bubbleSort function sorts an array of integers in ascending order. It works by comparing each pair of adjacent elements and swapping them if they are in the wrong order. This process repeats until no swaps are needed, indicating that the array is sorted.

Complexity

• Time Complexity: O(n²) in the average and worst case, where n is the number of items being sorted.
• Space Complexity: O(1) as it requires only a constant amount of additional space for variables.