An integer array arr is given. Rearrange all values in non-decreasing order by applying the bubble sort algorithm.
During every pass, adjacent values must be compared. Whenever a left value is greater than a right value, both values must be swapped. Return the sorted array.
Example 1
Input: arr = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: Larger values move right after adjacent swaps. Value 8 stays near the end, and values 5 and 4 move right until the final order becomes sorted.
Example 2
Input: arr = [7]
Output: [7]
Explanation: A single value already occupies the correct position, so no comparison or swap is required.
Brute Force Approach
Bubble sort begins with a very small idea: compare neighboring values and fix the pair when the order looks wrong. A single swap only repairs one local pair, but repeated local repairs slowly create global order.
After one complete pass, the largest value among the unsorted part reaches the far right. The far-right value no longer needs attention. Another pass then moves the next largest value to the position just before the final value.
Algorithm
The array length
nis stored so pass boundaries can be controlled.Every pass index from
0throughn - 2is processed because each pass places one large value near the end.The adjacent scan is limited to
n - pass - 1positions because the lastpassvalues are already fixed.Every pair
arr[current]andarr[current + 1]is compared so local disorder can be detected.Both adjacent values are exchanged when the left value is greater than the right value.
The next adjacent pair is checked after every comparison, and the largest remaining value keeps moving right through swaps.
The sorted array is returned after all required passes have been completed.
Dry Run
Bubble Sort Approach 1 Image
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts an integer array by repeated adjacent swaps. vector<int> bubbleSort(vector<int>& arr) { int n = arr.size(); // Each pass fixes one large value at the right boundary. for (int pass = 0; pass < n - 1; pass++) { // The fixed suffix is skipped during the adjacent scan. for (int current = 0; current < n - pass - 1; current++) { // Move larger left value right. if (arr[current] > arr[current + 1]) { swap(arr[current], arr[current + 1]); } } } return arr; }};// Driver codeint main() { // Input array vector<int> arr = {5, 1, 4, 2, 8}; // Solution object creation Solution obj; // Result printing vector<int> answer = obj.bubbleSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N2) in the best, average, and worst cases. The nested loops perform (N - 1) + (N - 2) + ... + 1 adjacent comparisons.
Space Complexity: O(1) auxiliary space, because only loop variables and one temporary value are maintained. The input array is rearranged in place.
Optimal Approach
The basic idea can be made kinder to already sorted data. During a pass, at least one swap should happen when unsorted pairs remain. A pass with zero swaps gives a quiet but powerful signal: every adjacent pair is already ordered.
A boolean flag named swapped records whether a pass changed the array. When no swap occurs, the algorithm stops immediately. The worst case remains quadratic, but a sorted array finishes after one scan.
The sorted suffix idea remains unchanged. The only improvement is early exit after a clean pass, so no unnecessary later passes are performed.
Algorithm
The array length
nis stored so pass boundaries and scan limits can be controlled.Every pass index from
0throughn - 2is considered, and a flag namedswappedis reset tofalsebefore the scan.The adjacent scan is limited to
n - pass - 1positions because earlier passes have already fixed the right suffix.Adjacent values are compared so a larger left value can be moved right through a swap.
The flag
swappedis markedtruewhenever a swap occurs during the current pass.The algorithm stops when a full pass finishes without a swap because all adjacent pairs are already in non-decreasing order.
The sorted array is returned after early completion or after every required pass has been processed.
Dry Run
Bubble Sort Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts an integer array with early stopping after a clean pass. vector<int> bubbleSort(vector<int>& arr) { int n = arr.size(); // Each pass fixes one large value at the right boundary. for (int pass = 0; pass < n - 1; pass++) { bool swapped = false; // The fixed suffix is skipped during the adjacent scan. for (int current = 0; current < n - pass - 1; current++) { // Move larger left value right. if (arr[current] > arr[current + 1]) { swap(arr[current], arr[current + 1]); swapped = true; } } // A clean pass proves complete adjacent order. if (!swapped) { break; } } return arr; }};// Driver codeint main() { // Input array vector<int> arr = {1, 2, 3, 4}; // Solution object creation Solution obj; // Result printing vector<int> answer = obj.bubbleSort(arr); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N²) in the average and worst cases because multiple passes and adjacent swaps may be required. In the best case, when the array is already sorted, the time complexity is O(N) because one complete pass performs N − 1 comparisons and the algorithm stops early.
Space Complexity: O(1) auxiliary space, because only loop variables, one temporary value, and the swapped flag are maintained. The input array is rearranged in place.
Interview follow-up Questions
Yes. Equal values are not swapped because the comparison uses > instead of >=. Equal values keep the original relative order after sorting.
Be the first to add a comment.