Bubble Sort solves the Sorting problem.
Bubble sort is an iterative algorithm that employs a brute-force strategy to sort a list by repeatedly comparing and swapping adjacent elements that are in the wrong order. With each pass through the array, the largest unsorted element "bubbles up" to its correct position at the end. Once the largest element is in place after the first pass, subsequent passes exclude it, progressively reducing the unsorted portion by one element each time. Due to this characteristic, bubble sort can be categorized as a decrease-and-conquer algorithm, although it is generally not considered an efficient or strong example of this technique. Passes through the array continue until only a single unsorted element remains, at which point the entire array is sorted.
To implement bubble sort, the algorithm maintains two pointers: an i pointer marks the boundary of the unsorted portion and indicates where the next largest element will settle. Initially, i points to the last element of the array. Another pointer, j, traverses the array from the beginning to the position just before i, comparing adjacent pairs of elements (j and j+1) and swapping them if they are out of order. After the j pointer passes i-1, the current iteration is complete, and the largest element from the unsorted portion of the array is now it its proper position i. The algorithm continues by decrementing i, resetting j to the start of the array, and beginning the next pass.
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}void bubbleSort(int arr[], int n) {
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}def bubble_sort(arr):
n = len(arr)
for i in range(n - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]To analyze the worst-case complexity of Bubble Sort, we examine how many comparisons and swaps are performed when the array is initially arranged in descending order (fully unsorted). This scenario represents Bubble Sort’s worst case because every possible swap needs to occur to achieve ascending order.
Bubble Sort operates by making multiple passes through the array. On each pass, it compares adjacent elements, swapping them if they are in the wrong order. Let's analyze each operation:
The total number of comparisons performed is thus the sum of the arithmetic series:
(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 = n(n - 1)/2 = O(n²).
Since each comparison might lead to a swap, in the worst case the number of swaps is the same as the number of comparisons. This leads to an overall worst-case time complexity of O(n²).
Notice that in the best case, even though the number of swaps would be 0 (if the array is already sorted), the number of comparisons is still n(n - 1)/2 = O(n²). Although this can be improved (see below), the average case of Bubble Sort is still O(n²). This quadratic complexity makes Bubble Sort inefficient for large datasets compared to more advanced algorithms like quicksort, mergesort, or heapsort, which have better average-case complexities.
Space Complexity: Bubble Sort operates in-place, only requiring a constant amount of additional space for i, j, and the temporary variable used while swapping elements. Thus, the space complexity is O(1).
Some versions of Bubble Sort bubble the smallest element to the beginning of the array instead of the largest element to the end. This does not change the time or space complexity of the algorithm.
The primary optimization for Bubble Sort involves adding an early termination check. This optimization leverages the fact that if during an entire pass through the array no swaps are required, the list must already be sorted, and the algorithm can immediately terminate.
To implement this optimization:
swapped) initialized
as false at the beginning of each pass.
swapped to true whenever a swap is performed.
swapped remains false, the
algorithm terminates early, as it indicates the array is already sorted.
This simple enhancement significantly improves Bubble Sort’s best-case
performance, changing it from O(n²) (in the non-optimized version)
to O(n), as it no longer unnecessarily completes additional passes.
[4, 2, 3, 1, 5]. Show
the state of the array after each pass through the array.