What is Bubble Sort?

Bubble Sort is a simple sorting algorithm where each element is compared with its adjacent element and swapped if they are in the wrong order. This process is repeated until the list is sorted.

Bubble Sort Steps

Step 1: Initialize the first pass by comparing the first two elements.
  1. If the first element is greater than the second, swap them.
  2. Otherwise, move to the next pair of elements.

Bubble Sort Example

Example:

Array before sorting: [5, 3, 8, 4, 2]

  1. Pass 1: Compare and swap elements to sort partially: [3, 5, 4, 2, 8]
  2. Pass 2: Continue sorting the unsorted part: [3, 4, 2, 5, 8]
  3. Pass 3: Repeat the process: [3, 2, 4, 5, 8]
  4. Final sorted array: [2, 3, 4, 5, 8]

Time and Space Complexity

Time Complexity:

  1. Worst Case: O(n²) - occurs when the array is in reverse order.
  2. Best Case: O(n) - occurs when the array is already sorted (optimized version only).
  3. Average Case: O(n²) - for random order of elements.

Space Complexity: O(1) - only requires a constant amount of additional space.

Pseudo Code for Bubble Sort

The following is the pseudo code for Bubble Sort:

Begin
  for each i from 1 to n
    for each j from 1 to n-i
      if arr[j] > arr[j+1]
        swap(arr[j], arr[j+1])
End

Bubble Sort Visualization

for(int i = 0; i < n-1; i++) {
    for(int j = 0; j < n-i-1; j++) {
        if(arr[j] > arr[j+1]) {
            // Swap arr[j] and arr[j+1]
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}
Home