Arrays - Bubble Sort in DSA

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements bubble to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position.

Speed:

 

Instructions: Click the "Sort" button to visualize the Bubble Sort algorithm. You can also adjust the speed of the visualization using the slider.

Algorithm

1. Start from the first element, compare the current element with the next element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element.
4. Repeat steps 1-3 until the array is sorted.
5. The array is sorted.
6. Exit.
7. The time complexity of the bubble sort is O(n²).
8. The space complexity of the bubble sort is O(1).

Pseudocode

Bubble Sort

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

Diagram

Example

Bubble Sort

function bubbleSort(arr) {
  let n = arr.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}

let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [ 11, 12, 22, 25, 34, 64, 90 ]

Complexity

• Time Complexity: O(n²)
  • Best Case: O(n)
  • Average Case: O(n²)
  • Worst Case: O(n²)
• Space Complexity: O(1)
• Stable: Yes

Live Example

function bubbleSort() {
  let arr = [64, 34, 25, 12, 22, 11, 90];
  let n = arr.length;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return (
    <div>
        <h3>Bubble Sort</h3>
        <p><b>Array:</b> [64, 34, 25, 12, 22, 11, 90]</p>
        <p>
            <b>Sorted Array:</b> [{arr.join(", ")}]
        </p>
    </div>
  )
}

Explanation

In the above example, we have an array of numbers [64, 34, 25, 12, 22, 11, 90]. We are using the bubble sort algorithm to sort the array in ascending order. The bubble sort algorithm compares each pair of adjacent items and swaps them if they are in the wrong order. The algorithm repeats this process until the array is sorted. The sorted array is [11, 12, 22, 25, 34, 64, 90]. The time complexity of the bubble sort is O(n²) and the space complexity is O(1).

Try it yourself

Change the array values and see how the bubble sort algorithm sorts the array.

📝 Note

Bubble sort is not a practical sorting algorithm when the input is large. It is not suitable for large datasets due to its O(n²) time complexity.

The main advantage of bubble sort is that it is easy to understand and implement. It is often used to teach the concept of sorting algorithms.

Bubble sort is stable, meaning that it preserves the relative order of equal elements.

Bubble sort is not an efficient algorithm for large datasets and is generally not used in practice.

References

• Wikipedia
• GeeksforGeeks
• Programiz
• TutorialsPoint
• StudyTonight
• w3schools

Related

Insertion Sort, Selection Sort, Merge Sort, Quick Sort, etc.

Quiz

1. What is the time complexity of the bubble sort algorithm?

   • O(n)
   • O(n²) ✔
   • O(log n)
   • O(n!)

2. Is bubble sort a stable sorting algorithm?

   • Yes ✔
   • No
   • Maybe
   • Not sure

3. What is the space complexity of the bubble sort algorithm?

   • O(n)
   • O(1) ✔
   • O(log n)
   • O(n!)

4. What is the main advantage of bubble sort?

   • It is the fastest sorting algorithm
   • It is easy to understand and implement ✔
   • It is suitable for large datasets
   • It is used in practice

5. What is the main disadvantage of bubble sort?

   • It is the fastest sorting algorithm
   • It is easy to understand and implement
   • It is not suitable for large datasets ✔
   • It is used in practice

Edge Cases

Important edge cases to consider when implementing or testing this algorithm. These cases are crucial for technical interviews and robust implementation.

Empty Input

high Impact

Handling arrays, strings, or collections that are empty

Single Element

high Impact

Processing with only one element in the input

Duplicate Values

medium Impact

Handling multiple identical elements in the input

Negative/Zero Values

high Impact

Dealing with negative numbers or zero values

Pre-sorted Data

medium Impact

Input that is already sorted or reverse-sorted

Boundary Constraints

high Impact

Values at the limits of data type ranges

Large Input

medium Impact

Testing with very large datasets

Special Characters

medium Impact

Strings containing special characters or whitespace

💡 Tip: Always test your implementation against these edge cases before considering it complete. Edge cases are a critical part of technical interviews and real-world software development.

Conclusion

In this tutorial, we learned about the bubble sort algorithm. We discussed the algorithm, pseudocode, diagram, example, complexity, and related concepts. We also implemented the bubble sort algorithm in JavaScript and saw a live example. We also discussed the advantages and disadvantages of the bubble sort algorithm. We hope you enjoyed this tutorial and found it helpful. Feel free to share your thoughts in the comments below.