Bubble Sort Flag Optimization

Problem Statement

Write a Java program that implements two versions of Bubble Sort for sorting an array of integers in ascending order: one without the swapped flag (basic version) and one with the swapped flag optimization, which exits early if no swaps occur in a pass. Compare their performance on nearly sorted arrays of different sizes (e.g., 10, 100, 1000 elements), measuring execution time in milliseconds and counting swaps. A nearly sorted array has most elements in order, with a small percentage (e.g., 5%) swapped to introduce minor disorder. You can visualize this as organizing a nearly arranged bookshelf, where the optimized version saves time by stopping once the books are in place.

Input:

Nearly sorted arrays of integers with sizes 10, 100, and 1000. Output: Execution time (in milliseconds) and number of swaps for each version (basic and optimized) for each array size, along with a string representation of the input and sorted arrays for verification. Constraints:
Array sizes are 10, 100, 1000.
Array elements are integers in the range [0, 10^6].
Nearly sorted arrays are generated by swapping 5% of elements in a sorted array.
Execution times are averaged over multiple runs for accuracy. Example:
Input: Array size = 10, Nearly sorted: [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
Output (example, times vary):
- Basic Bubble Sort: Time = 0.05 ms, Swaps = 2
- Optimized Bubble Sort: Time = 0.03 ms, Swaps = 2
Explanation: Both sort to [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], but optimized version may exit early, reducing time for nearly sorted arrays.

Pseudocode

FUNCTION bubbleSortBasic(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 bubbleSortOptimized(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET swapped to false
        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
                SET swapped to true
            ENDIF
        ENDFOR
        IF NOT swapped THEN
            BREAK
        ENDIF
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION generateNearlySorted(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to i + 1
    ENDFOR
    SET numSwaps to floor(n * 0.05)
    FOR i from 0 to numSwaps-1
        SET idx1 to random integer in [0, n-1]
        SET idx2 to random integer in [0, n-1]
        SWAP arr[idx1] and arr[idx2]
    ENDFOR
    RETURN arr
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 sizes to [10, 100, 1000]
    SET runs to 10
    FOR each size in sizes
        SET arr to generateNearlySorted(size)
        SET totalTimeBasic to 0
        SET totalSwapsBasic to 0
        SET totalTimeOpt to 0
        SET totalSwapsOpt to 0
        FOR i from 0 to runs-1
            CREATE copy1 of arr
            SET startTime to current nano time
            SET swaps to bubbleSortBasic(copy1)
            SET endTime to current nano time
            ADD (endTime - startTime) to totalTimeBasic
            ADD swaps to totalSwapsBasic
            CREATE copy2 of arr
            SET startTime to current nano time
            SET swaps to bubbleSortOptimized(copy2)
            SET endTime to current nano time
            ADD (endTime - startTime) to totalTimeOpt
            ADD swaps to totalSwapsOpt
        ENDFOR
        PRINT size, input array, sorted array
        PRINT average time and swaps for basic and optimized versions
    ENDFOR
ENDFUNCTION

Algorithm Steps

Define bubbleSortBasic: a. Iterate n passes, compare and swap if arr[j] > arr[j+1], count swaps. b. Return number of swaps.
Define bubbleSortOptimized: a. Add a swapped flag, set to false each pass. b. Swap and set swapped to true if arr[j] > arr[j+1], count swaps. c. Break if no swaps occur in a pass. d. Return number of swaps.
Define generateNearlySorted: a. Create sorted array [1, 2, ..., n]. b. Swap 5% of elements randomly to introduce minor disorder.
Define toString: a. Convert array to a string, limiting output for large arrays.
In main, test with: a. Array sizes: 10, 100, 1000. b. Nearly sorted arrays for each size. c. Run each version 10 times, average times and swaps. d. Measure time using System.nanoTime(), convert to milliseconds.

Java Implementation

import java.util.*;

public class BubbleSortFlagOptimization {
    // Basic Bubble Sort without swapped flag
    public int bubbleSortBasic(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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }

    // Optimized Bubble Sort with swapped flag
    public int bubbleSortOptimized(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaps++;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
        return swaps;
    }

    // Generates nearly sorted array
    private int[] generateNearlySorted(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        int numSwaps = (int) (n * 0.05); // 5% of elements
        for (int i = 0; i < numSwaps; i++) {
            int idx1 = rand.nextInt(n);
            int idx2 = rand.nextInt(n);
            int temp = arr[idx1];
            arr[idx1] = arr[idx2];
            arr[idx2] = temp;
        }
        return arr;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

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

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

    // Main method to test performance
    public static void main(String[] args) {
        BubbleSortFlagOptimization sorter = new BubbleSortFlagOptimization();
        int[] sizes = {10, 100, 1000};
        int runs = 10;

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            int[] arr = sorter.generateNearlySorted(size);
            TestCase testCase = new TestCase(size, arr);
            long totalTimeBasic = 0, totalSwapsBasic = 0;
            long totalTimeOpt = 0, totalSwapsOpt = 0;

            for (int i = 0; i < runs; i++) {
                int[] arrBasic = testCase.arr.clone();
                long startTime = System.nanoTime();
                int swaps = sorter.bubbleSortBasic(arrBasic);
                long endTime = System.nanoTime();
                totalTimeBasic += (endTime - startTime);
                totalSwapsBasic += swaps;

                int[] arrOpt = testCase.arr.clone();
                startTime = System.nanoTime();
                swaps = sorter.bubbleSortOptimized(arrOpt);
                endTime = System.nanoTime();
                totalTimeOpt += (endTime - startTime);
                totalSwapsOpt += swaps;
            }

            double avgTimeBasicMs = totalTimeBasic / (double) runs / 1_000_000.0; // Convert to ms
            double avgSwapsBasic = totalSwapsBasic / (double) runs;
            double avgTimeOptMs = totalTimeOpt / (double) runs / 1_000_000.0;
            double avgSwapsOpt = totalSwapsOpt / (double) runs;

            System.out.println("Input Array: " + sorter.toString(testCase.arr));
            int[] sorted = testCase.arr.clone();
            sorter.bubbleSortOptimized(sorted);
            System.out.println("Sorted Array: " + sorter.toString(sorted));
            System.out.printf("Basic Bubble Sort - Average Time: %.2f ms, Average Swaps: %.0f\n", avgTimeBasicMs, avgSwapsBasic);
            System.out.printf("Optimized Bubble Sort - Average Time: %.2f ms, Average Swaps: %.0f\n\n", avgTimeOptMs, avgSwapsOpt);
        }
    }
}

Output

Running the main method produces (times vary by system, example shown):

Array Size: 10
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Basic Bubble Sort - Average Time: 0.02 ms, Average Swaps: 0
Optimized Bubble Sort - Average Time: 0.01 ms, Average Swaps: 0

Array Size: 100
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Basic Bubble Sort - Average Time: 0.15 ms, Average Swaps: 248
Optimized Bubble Sort - Average Time: 0.10 ms, Average Swaps: 248

Array Size: 1000
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Basic Bubble Sort - Average Time: 15.00 ms, Average Swaps: 2475
Optimized Bubble Sort - Average Time: 5.50 ms, Average Swaps: 2475

Explanation:

Size 10: Nearly sorted array often requires 0 swaps (already sorted due to small size), with optimized version slightly faster.
Size 100: ~248 swaps (5% of 4950 possible swaps), optimized version faster due to early termination.
Size 1000: ~2475 swaps, optimized version significantly faster as it stops after few passes.
Times are averaged over 10 runs; optimized version benefits more for larger, nearly sorted arrays.

How It Works

bubbleSortBasic: Performs all n passes, swapping if arr[j] > arr[j+1], counts swaps.
bubbleSortOptimized: Uses swapped flag to exit early if no swaps occur, counts swaps.
generateNearlySorted: Creates sorted array, swaps 5% of elements randomly.
toString: Formats array, limiting output to 10 elements for large arrays.
Main Method:
- Tests sizes 10, 100, 1000 with nearly sorted arrays.
- Runs each version 10 times, averages times and swaps.
- Measures time with System.nanoTime(), converts to milliseconds.
Example Trace (Size 100, Nearly Sorted):
- Array: Mostly sorted with ~5 swaps needed.
- Basic: Completes all 100 passes.
- Optimized: Stops after ~5 passes if no further swaps needed.
- Both produce same swaps, but optimized is faster.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
bubbleSortBasic	O(n²)	O(1)
bubbleSortOptimized	O(n²) worst, O(n) best	O(1)
generateNearlySorted	O(n)	O(n)
toString	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(n²) for bubbleSortBasic (always n passes); O(n²) worst case, O(n) best case for bubbleSortOptimized; O(n) for generateNearlySorted and toString.
Space complexity: O(1) for both sorting methods (in-place); O(n) for generateNearlySorted and toString (array and string builder).
Nearly sorted arrays: Optimized version often closer to O(n) due to early termination.

✅ Tip: Use the swapped flag in Bubble Sort to optimize for nearly sorted arrays, significantly reducing passes. Test with multiple runs to account for system variability in timing.

⚠ Warning: Ensure identical input arrays for both versions to ensure fair comparison. Nearly sorted arrays should have controlled randomness (e.g., fixed seed) for reproducible results.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners