What is Bubble Sort?
Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means that the list is sorted. This algorithm gets its name because smaller elements “bubble” to the top of the list (beginning of the array) with each iteration.
What is the Complexity of Bubble Sort?
Its average and worst-case time complexity are both (O(n^2)), where (n) is the number of items being sorted. Here, (n^2) represents the situation where each element needs to be compared with every other element.
Despite its simplicity, Bubble Sort is not suitable for large datasets.
Java Implementation of Bubble Sort
Here’s how you can implement Bubble Sort in Java:
public class BubbleSortExample {
void bubbleSort(int arr[]) {
int n = arr.length;
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+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
// Method to test the sorting method
public static void main(String args[]) {
BubbleSortExample ob = new BubbleSortExample();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array:");
for (int i=0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}In this implementation, the bubbleSort method sorts an array of integers. It uses a nested loop where the inner loop performs the swapping of elements if they are in the wrong order, and the outer loop ensures the process repeats until the array is sorted. After sorting, the sorted array is printed to the console.
Output:
Sorted array:
11 12 22 25 34 64 90 Explanation
Outer Loop
for (int i = 0; i < n-1; i++)The outer loop runs from the beginning of the array to the second-to-last element. The variable i tracks the current iteration of the sort. With each complete pass through the array, the largest unsorted element “bubbles up” to its correct position at the end of the array, so with each subsequent pass, you need to check one less element.
Inner Loop
for (int j = 0; j < n-i-1; j++)The inner loop compares adjacent elements in the array. The condition n-i-1 ensures that the loop only goes up to the last unsorted element. As i increases (representing the number of sorted elements at the end of the array), the range of the inner loop decreases accordingly.
Comparison and Swap
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}Inside the inner loop, each pair of adjacent elements is compared. If an element is greater than the one following it (arr[j] > arr[j+1]), the two elements are swapped. This is done by temporarily storing one element in a variable temp, moving the second element to the first position, and then moving the stored element to the second position. This swap ensures that after each pass, the largest of the compared elements moves towards the end of the array.
Completion
After all the passes, when no more swaps are needed, the array becomes fully sorted in ascending order. The outer loop ensures the process repeats enough times to sort all elements. As elements are progressively sorted with each iteration, the algorithm needs fewer comparisons, hence the decreasing range of the inner loop.
Why is the Complexity of Bubble Sort (O(n^2))?
Here’s a step-by-step breakdown of how the algorithm works, which leads to its O(n^2) time complexity:
- Outer Loop: For each element in the array (n elements), the algorithm performs a pass to place the largest unsorted element in its correct position. This requires n-1 passes for an array of n elements. This is because after n-1 passes, the smallest element will already be in its correct position, assuming all other elements are in their correct positions as well.
- Inner Loop: On each pass, the algorithm compares adjacent elements and swaps them if they are in the wrong order. The number of comparisons in the first pass is n-1, then n-2 for the second pass, and so on, until there is 1 comparison in the last pass. The total number of comparisons (and potentially swaps) is the sum of the first n-1 integers, which is (n-1)n/2.
- Total Operations: The sum (n-1)n/2 is roughly n^2/2 – n/2. When analyzing algorithms, constants and lower order terms are usually ignored, as they don’t significantly affect the growth rate of the runtime. Therefore, the time complexity simplifies to O(n^2).
This quadratic time complexity means that the time to sort the elements grows quadratically as the number of elements n increases. This makes Bubble Sort inefficient on large lists and generally not recommended for practical use in situations where time efficiency is important. However, its simplicity makes it useful for educational purposes and in scenarios where the list is almost sorted, with only a few elements out of place.