Bubble Sort

Bubble Sort

The largest element “bubbles up” to its correct position in each pass.

Time Complexity: O(n^2).

Concept: Repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong order.

Steps

1. Compare adjacent elements and swap them if they are out of order.
2. Repeat the process until no swaps are made in a pass.

Example

Let’s sort the array [5, 2, 4, 6, 1, 3] using bubble sort.

Step-by-Step Walkthrough:

1. Initial array: [5, 2, 4, 6, 1, 3]

2. Pass 1 (i = 0):

   1. Compare 5, 2: Since 5 > 2, swap. Array: [2, 5, 4, 6, 1, 3]
   2. Compare 5, 4: Since 5 > 4, swap. Array: [2, 4, 5, 6, 1, 3]
   3. Compare 5, 6: No swap (5 < 6). Array: [2, 4, 5, 6, 1, 3]
   4. Compare 6, 1: Since 6 > 1, swap. Array: [2, 4, 5, 1, 6, 3]
   5. Compare 6, 3: Since 6 > 3, swap. Array: [2, 4, 5, 1, 3, 6]
   6. Largest element 6 is now at the end.

3. Pass 2 (i = 1):

   1. Compare 2, 4: No swap (2 < 4). Array: [2, 4, 5, 1, 3, 6]
   2. Compare 4, 5: No swap (4 < 5). Array: [2, 4, 5, 1, 3, 6]
   3. Compare 5, 1: Since 5 > 1, swap. Array: [2, 4, 1, 5, 3, 6]
   4. Compare 5, 3: Since 5 > 3, swap. Array: [2, 4, 1, 3, 5, 6]
   5. Second largest element 5 is now in place.

4. Pass 3 (i = 2):

   1. Compare 2, 4: No swap (2 < 4). Array: [2, 4, 1, 3, 5, 6]
   2. Compare 4, 1: Since 4 > 1, swap. Array: [2, 1, 4, 3, 5, 6]
   3. Compare 4, 3: Since 4 > 3, swap. Array: [2, 1, 3, 4, 5, 6]
   4. Third largest element 4 is now in place.

5. Pass 4 (i = 3):

   1. Compare 2, 1: Since 2 > 1, swap. Array: [1, 2, 3, 4, 5, 6]
   2. Compare 2, 3: No swap (2 < 3). Array: [1, 2, 3, 4, 5, 6]
   3. Array is now sorted, but the algorithm continues to check.

6. Pass 5 (i = 4):

   1. Compare 1, 2: No swap (1 < 2). Array: [1, 2, 3, 4, 5, 6]
   2. No swaps needed; array is sorted.

7. Final Sorted Array: [1, 2, 3, 4, 5, 6]

Explanation

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

1. A is the input array.
2. Outer loop i tracks the number of passes, ensuring the largest unsorted element moves to the end in each pass.
3. Inner loop j compares adjacent elements and swaps them if A[j] > A[j + 1].
4. Continue until no swaps are needed or the array is fully sorted.

Why is the upper limit of the inner loop n - i - 2 ?

1. Because, with every iteration of i, the element at the last will be the greatest number in the array.
2. With the first iteration of i, the greatest element will be at the last index.
3. With the second iteration of i, the second greatest element will be at the second from the last index.
4. …

Complexity analysis

1. Time Complexity: O(n²) in worst and average cases, O(n) in best case (already sorted array with no swaps).
2. Space Complexity: O(1) (in-place sorting).
3. Use Case: Simple to implement but inefficient for large datasets; best for small arrays or educational purposes.
4. Optimization: Can be improved by adding a flag to check if any swaps occurred in a pass. If no swaps, the array is sorted, and the algorithm can terminate early.
5. For comparison with insertion sort, bubble sort is generally less efficient because it performs more swaps and doesn’t adapt as well to partially sorted arrays.