What is Bubble Sort


​Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the list is sorted. It is called bubble sort because elements move through the list like bubbles rising to the surface.

Who invented it?

Bubble sort was first described by John von Neumann in 1945, although his work on the subject was unpublished until 1949. It is possible that the algorithm was invented earlier by someone else, but von Neumann's work is the earliest known description of the algorithm.

Pseudocode

Code Snippet Tabs 

procedure bubbleSort(list : array of items)
   n = length(list)
   repeat
      swapped = false
      for i = 1 to n-1 inclusive do
         if list[i] > list[i+1] then
            swap(list[i], list[i+1])
            swapped = true
         end if
      end for
      n = n - 1
   until not swapped
end procedure
Bubble sort Iterates through the list and compare adjacent pairs of elements. If the elements are out of order, swap them. After each pass through the list, the algorithm decrements the length of the list by 1 to exclude the last element, which is already in its correct position. The algorithm continues iterating through the list and swapping adjacent elements until no swaps are made during a pass through the list.

Sample Code

Code Snippet Tabs 
// C++ code snippet

void bubbleSort(int arr[], int n) {
   bool swapped;
   for (int i = 0; i < n-1; i++) {
      swapped = false;
      for (int j = 0; j < n-i-1; j++) {
         if (arr[j] > arr[j+1]) {
            swap(arr[j], arr[j+1]);
            swapped = true;
         }
      }
      if (swapped == false) {
         break;
      }
   }
}

int main() {
   int arr[] = {5, 2, 9, 1, 5, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   bubbleSort(arr, n);
   cout << "Sorted array: ";
   for (int i = 0; i < n; i++) {
      cout << arr[i] << " ";
   }
   return 0;
}

# Python code snippet
procedure bubbleSort(list : array of items)
   n = length(list)
   repeat
      swapped = false
      for i = 1 to n-1 inclusive do
         if list[i] > list[i+1] then
            swap(list[i], list[i+1])
            swapped = true
         end if
      end for
      n = n - 1
   until not swapped
end procedure
 

import java.util.Arrays;

public class BubbleSort {
   public static void bubbleSort(int[] arr) {
      int n = arr.length;
      boolean swapped;
      for (int i = 0; i < n-1; i++) {
         swapped = false;
         for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
               int temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
               swapped = true;
            }
         }
         if (swapped == false) {
            break;
         }
      }
   }

   public static void main(String[] args) {
      int[] arr = {5, 2, 9, 1, 5, 6};
      bubbleSort(arr);
      System.out.println("Sorted array: " + Arrays.toString(arr));
   }
}

Time and Space Complexity

The time complexity of Bubble Sort is O(n^2), where n is the number of elements in the list. This is because the algorithm performs n-1 passes through the list, with each pass comparing n-i-1 pairs of adjacent elements. The space complexity of Bubble Sort is O(1), because the algorithm only requires a constant amount of extra space to store temporary variables used in swapping elements.

Advantages

  • The main advantage of Bubble Sort is its simplicity and ease of implementation. It is also useful for small datasets, as its performance is not significantly worse than other sorting algorithms for small n.

Disadvantages

  • However, for large datasets, Bubble Sort's time complexity makes it inefficient compared to other sorting algorithms such as QuickSort or MergeSort.
Contact Us : [email protected]