Array Sorting

Problem Statement

Write a Java program that implements the bubble sort algorithm to sort an array of integers in ascending order. The program should modify the input array in-place to arrange its elements from smallest to largest and test the implementation with various input arrays, including empty arrays, single-element arrays, and arrays with duplicate or negative numbers. You can visualize this as organizing a row of books on a shelf by repeatedly comparing and swapping adjacent books to ensure they are in order by size.

Input: An array of integers (e.g., arr = [64, 34, 25, 12, 22]). Output: The array modified in-place to be sorted in ascending order (e.g., [12, 22, 25, 34, 64]). Constraints:

• The array length is between 0 and 10^5.
• Elements are integers between -10^9 and 10^9.
• The array may be empty. Example:
• Input: arr = [64, 34, 25, 12, 22]
• Output: [12, 22, 25, 34, 64]
• Explanation: The array is sorted in ascending order using bubble sort.
• Input: arr = [1, 1, 1]
• Output: [1, 1, 1]
• Explanation: The array with duplicate elements remains sorted.

Pseudocode

FUNCTION bubbleSort(arr)
    IF arr is null OR length of arr <= 1 THEN
        RETURN
    ENDIF
    SET n to length of arr
    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
            ENDIF
        ENDFOR
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testArrays to arrays of integers
    FOR each array in testArrays
        CALL bubbleSort(array)
        PRINT array
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input array is null or has 0 or 1 element. If so, return, as no sorting is needed.
2. Initialize n as the length of the array.
3. For each index i from 0 to n - 1: a. Iterate through indices j from 0 to n - i - 2. b. If arr[j] > arr[j + 1], swap the elements at indices j and j + 1 using a temporary variable.
4. Repeat until no more swaps are needed, indicating the array is sorted.
5. In the main method, create test arrays with various cases (e.g., unsorted, sorted, duplicates, negative numbers) and call bubbleSort to verify correctness.

Java Implementation

public class ArraySorting {
    // Sorts array in ascending order using bubble sort
    public void bubbleSort(int[] arr) {
        // Check for null or single-element/empty array
        if (arr == null || arr.length <= 1) {
            return;
        }
        // Get array length
        int n = arr.length;
        // Outer loop for passes
        for (int i = 0; i < n; i++) {
            // Inner loop for comparisons and swaps
            for (int j = 0; j < n - i - 1; j++) {
                // Compare adjacent elements
                if (arr[j] > arr[j + 1]) {
                    // Swap elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Main method to test bubbleSort with various arrays
    public static void main(String[] args) {
        ArraySorting sorter = new ArraySorting();

        // Test case 1: Unsorted array
        int[] arr1 = {64, 34, 25, 12, 22};
        System.out.print("Test case 1 before: ");
        printArray(arr1);
        sorter.bubbleSort(arr1);
        System.out.print("Test case 1 after: ");
        printArray(arr1);

        // Test case 2: Already sorted array
        int[] arr2 = {1, 2, 3, 4, 5};
        System.out.print("Test case 2 before: ");
        printArray(arr2);
        sorter.bubbleSort(arr2);
        System.out.print("Test case 2 after: ");
        printArray(arr2);

        // Test case 3: Array with duplicates
        int[] arr3 = {3, 1, 3, 2, 1};
        System.out.print("Test case 3 before: ");
        printArray(arr3);
        sorter.bubbleSort(arr3);
        System.out.print("Test case 3 after: ");
        printArray(arr3);

        // Test case 4: Array with negative numbers
        int[] arr4 = {-5, 0, -2, 3, -1};
        System.out.print("Test case 4 before: ");
        printArray(arr4);
        sorter.bubbleSort(arr4);
        System.out.print("Test case 4 after: ");
        printArray(arr4);

        // Test case 5: Empty array
        int[] arr5 = {};
        System.out.print("Test case 5 before: ");
        printArray(arr5);
        sorter.bubbleSort(arr5);
        System.out.print("Test case 5 after: ");
        printArray(arr5);

        // Test case 6: Single-element array
        int[] arr6 = {42};
        System.out.print("Test case 6 before: ");
        printArray(arr6);
        sorter.bubbleSort(arr6);
        System.out.print("Test case 6 after: ");
        printArray(arr6);
    }

    // Helper method to print array
    private static void printArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            System.out.println("[]");
            return;
        }
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1 before: [64, 34, 25, 12, 22]
Test case 1 after: [12, 22, 25, 34, 64]
Test case 2 before: [1, 2, 3, 4, 5]
Test case 2 after: [1, 2, 3, 4, 5]
Test case 3 before: [3, 1, 3, 2, 1]
Test case 3 after: [1, 1, 2, 3, 3]
Test case 4 before: [-5, 0, -2, 3, -1]
Test case 4 after: [-5, -2, -1, 0, 3]
Test case 5 before: []
Test case 5 after: []
Test case 6 before: [42]
Test case 6 after: [42]

Explanation:

• Test case 1: Sorts [64, 34, 25, 12, 22] to [12, 22, 25, 34, 64].
• Test case 2: Already sorted [1, 2, 3, 4, 5] remains unchanged.
• Test case 3: Sorts [3, 1, 3, 2, 1] to [1, 1, 2, 3, 3], handling duplicates.
• Test case 4: Sorts [-5, 0, -2, 3, -1] to [-5, -2, -1, 0, 3], handling negatives.
• Test case 5: Empty array [] remains unchanged.
• Test case 6: Single-element array [42] remains unchanged.

How It Works

• Step 1: The bubbleSort method checks if the array is null or has 0 or 1 element. For [64, 34, 25, 12, 22], it proceeds.
• Step 2: For n = 5, perform 5 passes:
  • Pass 1: Compare and swap adjacent elements: [64, 34] → [34, 64], [64, 25] → [25, 64], [64, 12] → [12, 64], [64, 22] → [22, 64]. Result: [34, 25, 12, 22, 64].
  • Pass 2: [34, 25] → [25, 34], [34, 12] → [12, 34], [34, 22] → [22, 34]. Result: [25, 12, 22, 34, 64].
  • Pass 3: [25, 12] → [12, 25], [25, 22] → [22, 25]. Result: [12, 22, 25, 34, 64].
  • Pass 4: No swaps needed, array is sorted.
  • Pass 5: No swaps needed, done.
• Example Trace: For [64, 34, 25, 12, 22], sorts to [12, 22, 25, 34, 64] by bubbling larger elements to the end.
• Main Method: Tests the method with unsorted, sorted, duplicate, negative, empty, and single-element arrays, printing results.
• In-Place Property: Bubble sort modifies the array in-place, using only a temporary variable for swaps.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n^2) in the worst and average cases, as the algorithm performs up to n passes, each with up to n-1 comparisons. Best case is O(n) when the array is already sorted (no swaps).
• Space complexity: O(1), as only a temporary variable is used for swapping.
• Worst case: O(n^2) for reverse-sorted arrays. Best case: O(n) for sorted arrays.

✅ Tip: Bubble sort is simple but inefficient for large arrays. Consider adding a flag to detect if no swaps occur in a pass to optimize for nearly sorted arrays. Test with various cases to ensure correctness.

⚠ Warning: Ensure the input array is not null to avoid NullPointerException. Be cautious with very large arrays, as O(n^2) time complexity can lead to slow performance.