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

Bubble Sort Edge Case Handling

Problem Statement

Write a Java program that enhances the Bubble Sort implementation to sort arrays containing negative numbers and floating-point numbers in ascending order, using the optimized version with the swapped flag. The program should count the number of swaps performed and test with diverse inputs, including arrays with negative integers, floating-point numbers, mixed positive/negative numbers, empty arrays, and single-element arrays. The enhanced implementation should use generics to support comparable types, focusing on Double to handle both negative and floating-point numbers. You can visualize this as organizing a list of measurements (e.g., temperatures or scores) that include decimals and negative values, ensuring the algorithm handles all cases correctly.

Input:

  • Arrays of Double values, including negative numbers, floating-point numbers, and mixed cases. Output: The sorted array (in ascending order), 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 Double values in the range [-10^9, 10^9], including floating-point numbers. Example:
  • Input: array = [64.5, -34.2, 25.0, -12.7, 22.3]
  • Output:
    • Input Array: [64.5, -34.2, 25.0, -12.7, 22.3]
    • Sorted Array: [-34.2, -12.7, 22.3, 25.0, 64.5]
    • Swaps: 6
  • Explanation: Bubble Sort sorts negative and floating-point numbers, requiring 6 swaps.
  • Input: array = [-1.5, -2.5, -3.5]
  • Output:
    • Input Array: [-1.5, -2.5, -3.5]
    • Sorted Array: [-3.5, -2.5, -1.5]
    • Swaps: 3
  • Explanation: Negative floating-point numbers sorted, 3 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
        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 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 (generic): a. Accept an array of Comparable<T> type (use Double for testing). b. Initialize a counter swaps to 0 and a swapped flag. c. For each pass i from 0 to n-1:
    • Compare adjacent elements using compareTo, swap if arr[j] > arr[j+1].
    • Increment swaps and set swapped to true if a swap occurs.
    • Break if no swaps in a pass. d. Return the number of swaps.
  2. Define toString: a. Convert the array to a string, e.g., "[64.5, -34.2, 25.0]".
  3. In main, test with: a. Mixed positive/negative floating-point numbers. b. Negative floating-point numbers. c. Mixed positive/negative integers. d. Empty array. e. Single-element array. f. Array with duplicate floating-point numbers.

Java Implementation

import java.util.*;

public class BubbleSortEdgeCaseHandling {
    // Optimized Bubble Sort for Comparable types
    public <T extends Comparable<T>> int bubbleSort(T[] 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].compareTo(arr[j + 1]) > 0) {
                    // Swap elements
                    T temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaps++;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
        return swaps;
    }

    // Converts array to string
    public <T> String toString(T[] 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 {
        Double[] arr;

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

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

        // Test cases
        TestCase[] testCases = {
            new TestCase(new Double[]{64.5, -34.2, 25.0, -12.7, 22.3}), // Mixed positive/negative floats
            new TestCase(new Double[]{-1.5, -2.5, -3.5}),                 // Negative floats
            new TestCase(new Double[]{-5.0, 3.0, -2.0, 0.0, 10.0}),      // Mixed integers
            new TestCase(new Double[]{}),                                  // Empty
            new TestCase(new Double[]{42.5}),                             // Single element
            new TestCase(new Double[]{2.5, 1.0, 2.5, 1.5, 1.0})          // Duplicates
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            Double[] 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.5, -34.2, 25.0, -12.7, 22.3]
Sorted Array: [-34.2, -12.7, 22.3, 25.0, 64.5]
Swaps: 6

Test case 2:
Input Array: [-1.5, -2.5, -3.5]
Sorted Array: [-3.5, -2.5, -1.5]
Swaps: 3

Test case 3:
Input Array: [-5.0, 3.0, -2.0, 0.0, 10.0]
Sorted Array: [-5.0, -2.0, 0.0, 3.0, 10.0]
Swaps: 3

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

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

Test case 6:
Input Array: [2.5, 1.0, 2.5, 1.5, 1.0]
Sorted Array: [1.0, 1.0, 1.5, 2.5, 2.5]
Swaps: 5

Explanation:

  • Test case 1: Mixed positive/negative floats, 6 swaps to sort.
  • Test case 2: Negative floats, 3 swaps (reversed order).
  • Test case 3: Mixed integers, 3 swaps.
  • Test case 4: Empty array, 0 swaps.
  • Test case 5: Single element, 0 swaps.
  • Test case 6: Duplicates, 5 swaps.

How It Works

  • bubbleSort:
    • Uses generics with Comparable<T> to handle Double (floating-point and negative numbers).
    • Compares with compareTo, swaps if arr[j] > arr[j+1], counts swaps.
    • Exits early if no swaps occur (optimized).
  • toString: Formats array as a string, handling Double values.
  • Example Trace (Test case 1):
    • Pass 1: [64.5, -34.2, 25.0, -12.7, 22.3] → [-34.2, 25.0, -12.7, 22.3, 64.5] (3 swaps: 64.5↔-34.2, -34.2↔25.0, 25.0↔-12.7).
    • Pass 2: [-34.2, 25.0, -12.7, 22.3, 64.5] → [-34.2, -12.7, 22.3, 25.0, 64.5] (2 swaps: 25.0↔-12.7, -12.7↔22.3).
    • Pass 3: [-34.2, -12.7, 22.3, 25.0, 64.5] → [-34.2, -12.7, 22.3, 25.0, 64.5] (0 swaps, exit).
    • Total swaps: 6.
  • Main Method: Tests mixed floats, negative floats, mixed integers, empty, single element, and duplicates.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
bubbleSortO(n²) worst, O(n) bestO(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for bubbleSort in worst case, O(n) in best case (already sorted); O(n) for toString.
  • Space complexity: O(1) for bubbleSort (in-place); O(n) for toString (string builder).
  • Generics ensure flexibility without changing complexity.

✅ Tip: Use generics with Comparable to handle negative and floating-point numbers in Bubble Sort. The swapped flag optimization improves performance for nearly sorted arrays.

⚠ Warning: Ensure input arrays contain valid Double values to avoid NullPointerException in comparisons. Test edge cases like empty or single-element arrays to verify robustness.