Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Basic Bubble Sort

Problem Statement

Write a Java program that implements the Bubble Sort algorithm to sort an array of integers in ascending order. The program should count the number of swaps performed during sorting and test the implementation with various input arrays, including unsorted, already sorted, reversed, and arrays with duplicate elements. Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, bubbling larger elements to the end. You can visualize this as bubbles rising in a glass, pushing larger numbers to the end with each pass.

Input:

  • An array of integers to be sorted. Output: The sorted array, the number of swaps performed, and a string representation of the input and sorted arrays for clarity. Constraints:
  • The array length n is between 0 and 10^5.
  • Array elements are integers in the range [-10^9, 10^9]. Example:
  • Input: array = [64, 34, 25, 12, 22]
  • Output:
    • Input Array: [64, 34, 25, 12, 22]
    • Sorted Array: [12, 22, 25, 34, 64]
    • Swaps: 7
  • Explanation: Bubble Sort performs passes, swapping adjacent elements if out of order, resulting in 7 swaps.
  • Input: array = [1, 2, 3]
  • Output:
    • Input Array: [1, 2, 3]
    • Sorted Array: [1, 2, 3]
    • Swaps: 0
  • Explanation: Already sorted array requires no swaps.

Pseudocode

FUNCTION bubbleSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        FOR j from 0 to n-i-2
            IF arr[j] > arr[j+1] THEN
                SET temp to arr[j]
                SET arr[j] to arr[j+1]
                SET arr[j+1] to temp
                INCREMENT swaps
            ENDIF
        ENDFOR
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input arrays
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET swaps to bubbleSort(copy)
        PRINT input array, sorted array, and swaps
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define bubbleSort: a. Initialize a counter swaps to 0. b. For each pass i from 0 to n-1:
    • Compare adjacent elements j and j+1 from 0 to n-i-2.
    • If arr[j] > arr[j+1], swap them and increment swaps. c. Return the number of swaps.
  2. Define toString: a. Convert the array to a string, e.g., "[64, 34, 25, 12, 22]".
  3. In main, test with: a. An unsorted array. b. An already sorted array. c. A reversed array. d. An array with duplicates. e. An empty array.

Java Implementation

import java.util.*;

public class BasicBubbleSort {
    // Performs Bubble Sort and counts swaps
    public int bubbleSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i]);
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;

        TestCase(int[] arr) {
            this.arr = arr;
        }
    }

    // Main method to test Bubble Sort
    public static void main(String[] args) {
        BasicBubbleSort sorter = new BasicBubbleSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}), // Unsorted
            new TestCase(new int[]{1, 2, 3, 4, 5}),      // Sorted
            new TestCase(new int[]{5, 4, 3, 2, 1}),      // Reversed
            new TestCase(new int[]{3, 1, 3, 2, 1}),      // Duplicates
            new TestCase(new int[]{})                     // Empty
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            int swaps = sorter.bubbleSort(arr);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Swaps: " + swaps + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input Array: [64, 34, 25, 12, 22]
Sorted Array: [12, 22, 25, 34, 64]
Swaps: 7

Test case 2:
Input Array: [1, 2, 3, 4, 5]
Sorted Array: [1, 2, 3, 4, 5]
Swaps: 0

Test case 3:
Input Array: [5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5]
Swaps: 10

Test case 4:
Input Array: [3, 1, 3, 2, 1]
Sorted Array: [1, 1, 2, 3, 3]
Swaps: 6

Test case 5:
Input Array: []
Sorted Array: []
Swaps: 0

Explanation:

  • Test case 1: Unsorted array requires 7 swaps to sort.
  • Test case 2: Already sorted array requires 0 swaps.
  • Test case 3: Reversed array requires 10 swaps (maximum for n=5).
  • Test case 4: Array with duplicates requires 6 swaps.
  • Test case 5: Empty array requires 0 swaps.

How It Works

  • bubbleSort:
    • Iterates through the array, comparing adjacent elements.
    • Swaps if out of order, incrementing swaps.
    • Each pass ensures the largest unsorted element moves to its correct position.
  • toString: Formats array as a string for output.
  • Example Trace (Test case 1):
    • Pass 1: [64, 34, 25, 12, 22] → [34, 25, 12, 22, 64] (3 swaps: 64↔34, 34↔25, 25↔12).
    • Pass 2: [34, 25, 12, 22, 64] → [25, 12, 22, 34, 64] (2 swaps: 34↔25, 25↔12).
    • Pass 3: [25, 12, 22, 34, 64] → [12, 22, 25, 34, 64] (2 swaps: 25↔12, 25↔22).
    • Passes 4-5: No swaps, array sorted. Total swaps: 7.
  • Main Method: Tests unsorted, sorted, reversed, duplicates, and empty arrays.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
bubbleSortO(n²)O(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for bubbleSort (n passes, up to n-1 comparisons/swaps each); O(n) for toString (iterate array).
  • Space complexity: O(1) for bubbleSort (in-place); O(n) for toString (string builder).
  • Worst case: O(n²) time for reversed arrays; best case: O(n) time for sorted arrays.

✅ Tip: Bubble Sort is simple but inefficient for large arrays. Use it for small datasets or educational purposes. Tracking swaps helps understand the algorithm’s behavior.

⚠ Warning: Ensure the array is not modified unintentionally by creating a copy for sorting. Handle empty arrays to avoid index issues.