Bubble Sort

Intuition

The bubble sort algorithm sorts an array by repeatedly swapping adjacent elements if they are in the wrong order. The largest elements "bubble" to the end of the array with each pass.

Approach

Run a loop i from 0 to n-1.
Run a nested loop from j from 0 to n-i-1.
If arr[j] > arr[j+1], swap them.
Continue until the array is sorted.

Note: Here, after each iteration, the array becomes sorted up to the last index of the range. That is why the last index of the range decreases by 1 after each iteration. This decrement is managed by the outer loop, where the last index is represented by the variable i. The inner loop (variable j) helps to push the maximum element of the range [0...i] to the last index (i.e., index i).

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
      // Bubble sort Functin
    vector<int> bubbleSort(vector<int>& nums) {
        int n = nums.size();
        // Traverse through the array
        for (int i = n - 1; i >= 0; i--) {
            // Track if swaps are made 
            bool didSwap = false;
            for (int j = 0; j <= i - 1; j++) {
                // Swap if next element is smaller
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                    didSwap = true;
                }
            }
            /**  Break out of loop 
         if no swaps done*/
            if (!didSwap) {
                break;
            }
        }
        return nums;
    }
};

int main() {
    // Create an instance of solution 
    Solution solution;
    
    vector<int> nums = {7, 4, 1, 5, 3};
    
    cout << "Before Using Bubble Sort: " << endl;
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    // Function call for Bubble Sort
    nums = solution.bubbleSort(nums);

    cout << "Array After Using Bubble Sort: " << endl;
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

import java.util.*;

class Solution {
// Bubble Sort Function
    public int[] bubbleSort(int[] nums) {
        int n = nums.length;
        // Traverse through the array
        for (int i = n - 1; i >= 0; i--) {
            // Track if swaps are made
            boolean isSwapped = false;
            for (int j = 0; j <= i - 1; j++) {
                // Swap if next element is smaller
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    isSwapped = true;
                }
            }
            /** Break out of loop 
          if no swaps done*/
            if (!isSwapped) {
                break;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        // Create an instance of solution class
        Solution solution = new Solution();

        int[] nums = {7, 4, 1, 5, 3};

        System.out.println("Array Before Using Bubble Sort: " + Arrays.toString(nums));

        // Function call for Bubble Sort
        nums = solution.bubbleSort(nums);

        System.out.println("Array After Using Bubble Sort: " + Arrays.toString(nums));
    }
}

class Solution:
     # Bubble Sort Function
    def bubbleSort(self, nums):
        n = len(nums)
        # Traverse through the array
        for i in range(n - 1, -1, -1):
            # Track if swaps are made
            isSwapped = False
            for j in range(i):
                # Swap if next element is smaller
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    isSwapped = True
            ''' Break out of loop
             if no swaps done'''
            if not isSwapped:
                break
        return nums

# Main function
if __name__ == "__main__":
    # Create an instance of solution class
    solution = Solution()

    nums = [7, 4, 1, 5, 3]

    print("Array Before Using Bubble Sort:", nums)

    # Function call for Bubble Sort
    sorted_nums = solution.bubble_sort(nums)

    print("Array After Using Bubble Sort:", sorted_nums)
class Solution {
// Bubble  Sort Function
    bubbleSort(nums) {
        let n = nums.length;
        // Traverse through the array
        for (let i = n - 1; i >= 0; i--) {
            // Track if swaps are made
            let isSwapped = false;
            for (let j = 0; j <= i - 1; j++) {
                // Swap if next element is smaller
                if (nums[j] > nums[j + 1]) {
                    [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                    isSwapped = true;
                }
            }
            /** Break out of loop
          if no swaps done*/
            if (!isSwapped) {
                break;
            }
        }
        return nums;
    }
}

// Create an instance of solution class
let solution = new Solution();

let nums = [7, 4, 1, 5, 3];

console.log("Array Before Using Bubble Sort:", nums);

// Call the bubbleSort function
nums = solution.bubbleSort(nums);

console.log("Array After Using Bubble Sort:", nums);

Complexity Analysis:

Time Complexity: O(N²) for the worst and average cases and O(N) for the best case. Here, N is the size of the array.

Space Complexity: O(1), because Bubble Sort is an in-place sorting algorithm, meaning it only requires a constant amount of extra space for its operations, regardless of the size of the input array.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code