Bubble Sort

Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is an elementary sorting algorithm that is not suitable for large datasets due to its high time complexity. The algorithm is named "Bubble Sort" because the smaller elements "bubble" to the beginning of the list, while the larger elements "sink" to the end.

Algorithm

The Bubble Sort algorithm works as follows:

   Start at the beginning of the list.
   Compare each pair of adjacent elements in the list.
   If the elements are in the wrong order (i.e., the first element is greater than the second element), swap them.
   Continue this process until the end of the list is reached.
   If any elements were swapped during the pass, repeat steps 1-4.
   If no elements were swapped during a pass, the list is sorted, and the algorithm terminates.

Pseudocode

Here is a simple pseudocode for Bubble Sort:

function bubbleSort(arr)
  do
    swapped = false
    for i = 1 to length(arr) - 1
      if arr[i-1] > arr[i]
        swap(arr[i-1], arr[i])
        swapped = true
      end if
    end for
  while swapped
end function

Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst and average cases, where n is the number of elements in the list. In the best case (when the list is already sorted), the time complexity is O(n) since the algorithm can be easily modified to terminate early if no swaps were performed during a pass.

Space Complexity

The space complexity of Bubble Sort is O(1) because it is an in-place sorting algorithm, meaning it does not require additional memory for temporary storage.

C++ Example

Here is an example implementation of Bubble Sort in C++:

#include <iostream>

#include <vector>

void bubbleSort(std::vector < int > & arr) {
    bool swapped;
    do {
        swapped = false;
        for (size_t i = 1; i < arr.size(); ++i) {
            if (arr[i - 1] > arr[i]) {
                std::swap(arr[i - 1], arr[i]);
                swapped = true;
            }
        }
    } while (swapped);
}

int main() {
    std::vector < int > arr = {
        64,
        34,
        25,
        12,
        22,
        11,
        90
    };
    bubbleSort(arr);

    std::cout << "Sorted array is: ";
    for (int i: arr) {
        std::cout << i << " ";
    }

    return 0;
}

See Also

• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort