Bubble Sort

Bubble Sort is a simple and intuitive sorting algorithm, ideal for beginners to understand the basic concepts of sorting. It repeatedly compares adjacent elements and swaps them if they are in the wrong order, causing larger elements to "bubble" up to the end of the array. This article explains the principle and steps of Bubble Sort in detail, providing code examples in C and Go to help beginners get started quickly.

Principle

The core idea of Bubble Sort is:

1. Iterate through the array, comparing adjacent elements. If they are out of order (e.g., the first is greater than the second in ascending sort), swap them.
2. After each iteration, the largest element "bubbles" to the end of the unsorted portion.
3. Shrink the unsorted portion of the array and repeat the process until the entire array is sorted.

Its time complexity is O(n²), where n is the length of the array. Although it is less efficient than Quick Sort or Merge Sort in practice, its simplicity makes it an ideal starting point for learning algorithms.

Steps

Assuming we want to sort an integer array in ascending order, here are the detailed steps for Bubble Sort:

1. Initialization: Start from the first element of the array and compare it with the next one.
2. Compare and Swap: If the current element is greater than the next element, swap them.
3. Complete One Pass: Iterate through the entire unsorted portion, moving the largest element to its correct position at the end.
4. Update Range: Shrink the unsorted portion by one element from the end (as the largest element is now in place).
5. Repeat: Repeat steps 2-4 for the remaining unsorted portion until the entire array is sorted.

Implementation

C

Here is the C implementation of Bubble Sort, with detailed comments to aid understanding.

main.c

#include <stdio.h>

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    
    // Outer loop: controls the number of passes
    for (i = 0; i < n-1; i++) {
        // Inner loop: compares and swaps adjacent elements
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap adjacent elements
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// Helper function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test bubble sort
int main() {
    int arr[] = = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Compile & Run

$ gcc -o bin/bubble-sort main.c
$ bin/bubble-sort 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
$ 

Go

Here is the Go implementation of Bubble Sort, with detailed comments to aid understanding.

main.go

package main

import "fmt"

// bubbleSort implements the bubble sort algorithm
func bubbleSort(arr []int) {
    n := len(arr)
    
    // Outer loop: controls the number of passes
    for i := 0; i < n-1; i++ {
        // Inner loop: compares and swaps adjacent elements
        for j := 0; j < n-i-1; j++ {
            if (arr[j] > arr[j+1]) {
                // Swap adjacent elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

// printArray prints the elements of an array
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // Example array
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("Original array: ");
    printArray(arr)
    
    bubbleSort(arr)
    
    fmt.Print("Sorted array: ");
    printArray(arr)
}

$ gsk build -v
create bubble-sort/bin/bubble-sort-linux-amd64
$ ./bin/bubble-sort-linux-amd64 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Summary

The core of Bubble Sort is to sort an array by repeatedly comparing and swapping adjacent elements, causing the larger elements to "bubble" to the end of the unsorted portion.

---

Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.

Author: afxcn

Source: https://gostartkit.com/docs/algo/bubble-sort

Date Published: June 26, 2025