The bubble sort, also known as “Sinking Sort” algorithm is one of the simplest algorithms when it comes to sorting data.

Explanation:

Let’s assume that we have an array “A” that contains “N” number of elements.
The indexes of the elements in the array “A”, would be 0 to N-1.

In bubble sort, the two nearest elements of the array are compared, if the value is out of order, in this case, the smallest value comes after the bigger one, then the swapping of the two elements occurs. This action keeps reaping until no swapping is needed, which indicates that the array or the list is sorted out.

Because of the biggest or the smallest value bubbles up on top of the list, this is called “Bubble Sort”. This algorithm falls into the category of “comparison sort”, where the comparison of elements is used to sort a list.

Implementation:

  • Go
  • Python
  • C
  • import "fmt"
    func BubbleSortAlgorithm()  {
    result := BubbleSort([]int{2, 5, 6, 4, 7, 3, 9, 8})
    fmt.Println(result)
    }
    /*
    The function takes an array of integer as an argument,
    and performs bubble sort.
    */
    func BubbleSort(array []int) []int {
    // Get total length of array
    arrayLength := len(array)
    // Return if the array contains only 1 element
    if arrayLength < 1 {
    return array
    }
    // loop through all the elements and "bubble up"
    // the biggest value
    for i := 0; i < arrayLength-1; i++ { // Get the next element index nextI := i+1 // Compare the current and next element if the // value if out of order, then swap if array[i] > array[nextI] {
    Swap(array, i, nextI)
    }
    }
    // Keeps reaping until array contains only 1 element.
    BubbleSort(array[:arrayLength-1])
    return array
    }
    /*
    The function takes an array of an integer as an argument,
    as well as two indexes. The function performs swapping of
    the two elements specified in the argument.
    */
    func Swap(array []int, firstElement, lastElement int) []int {
    temp := array[firstElement]
    array[firstElement] = array[lastElement]
    array[lastElement] = temp
    return array
    }
  • def bubble_sort(array):
    """
    The function takes an array as an argument.
    It enumerates over the array and sorts them.
    When the whole array is sorted out it returns
    the list back to the calling function.
    :param array: List
    :return: List
    """
    for index, value in enumerate(array):
    next_index = index + 1
    if next_index < len(array) and value > array[next_index]:
    swap(array, index, next_index)
    bubble_sort(array)
    return array
    def swap(arr, i, next_i):
    """
    The function takes an array and two indexes as arguments, and swaps them.
    :param arr: List
    :param i: Integer
    :param next_i: Integer
    :return: List
    """
    temp = arr[i]
    arr[i] = arr[next_i]
    arr[next_i] = temp
    if __name__ == "__main__":
    print(bubble_sort([2, 5, 6, 4, 7, 3, 9, 8]))
  • #include <stdio.h>
    /**
    * The function takes an array and two integer indexes as
    * arguments and swaps two elements.
    *
    * @param array      An array
    * @param index      The first element
    * @param next_index The second element
    */
    void swap(int array[], int index, int next_index) {
    int temp = array[index];
    array[index] = array[next_index];
    array[next_index] = temp;
    return;
    }
    /**
    * The function takes an array and the length of the array as
    * arguments and performs bubble sort operation.
    *
    * @param array  The array that needs to be sorted
    * @param length The length of the array
    */
    void bubbleSort(int array[], int length) {
    // if the length is 1, return to previous call
    if (length == 1) {
    return;
    }
    // loop through all the elements and sort them
    for (int index = 0; index < length - 1; index++) { int next_index = index + 1; // if the next index is samller, then swap them if (array[index] > array[next_index]) {
    swap(array, index, next_index);
    }
    }
    // Kepp doing it!
    bubbleSort(array, length - 1);
    return;
    }
    /**
    * A simple function to print the list of an array.
    * @param array  Array that needs to be printed
    * @param length The length of the array
    */
    void printArray(int array[], int length) {
    printf("[");
    for (int i = 0; i < length; i++) {
    printf(" %d", array[i]);
    }
    printf(" ]\n");
    }
    int main(void) {
    int array[8] = {2, 5, 6, 4, 7, 3, 9, 8};
    int length = sizeof(array)/sizeof(int); // Array length calculation
    bubbleSort(array, length);
    printArray(array, length);
    return 0;
    }
    

The output of the program above,

[ 2 3 4 5 6 7 8 9 ]

Complexity Analysis:

  • Time Complexity

    Best-case: Ω(n)

    Average-case: θ(n²)

    Worst-case: Ο(n²)

  • Space Complexity

    Worst-case: Ο(1) ( which is excellent! )

Conclusion:

Due to the simplicity of the algorithm, it is used mostly as an introductory algorithm for people who wants to learn algorithmic computations. Otherwise, the bubble sort algorithm is way too slow to be implemented where speed is of the essence. Sometimes it is used to sort a list which is partially sorted and would occasionally have unsorted data.