Descending Bubble Sort

Problem Statement

Write a Java program that modifies the Bubble Sort implementation to sort an array of integers in descending order (largest to smallest). The program should count the number of swaps performed during sorting and test the implementation with arrays of different sizes and contents, including unsorted, already sorted (in descending order), reversed (ascending order), arrays with duplicate elements, and empty arrays. Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, bubbling smaller elements to the end for descending order. You can visualize this as bubbles sinking in a glass, pushing smaller numbers to the end with each pass.

Input:

An array of integers to be sorted in descending order. Output: The sorted array (in descending 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 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: [64, 34, 25, 22, 12]
- Swaps: 4
Explanation: Bubble Sort performs passes, swapping adjacent elements if the first is smaller, resulting in 4 swaps.
Input: array = [5, 4, 3, 2, 1]
Output:
- Input Array: [5, 4, 3, 2, 1]
- Sorted Array: [5, 4, 3, 2, 1]
- Swaps: 0
Explanation: Already sorted in descending order, no swaps needed.

Pseudocode

FUNCTION bubbleSortDescending(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 bubbleSortDescending(copy)
        PRINT input array, sorted array, and swaps
    ENDFOR
ENDFUNCTION

Algorithm Steps

Define bubbleSortDescending: 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 to sort in descending order. c. Return the number of swaps.
Define toString: a. Convert the array to a string, e.g., "[64, 34, 25, 22, 12]".
In main, test with: a. An unsorted array (medium size, n=5). b. An already sorted array (descending, n=5). c. A reversed array (ascending, n=5). d. An array with duplicates (n=6). e. An empty array (n=0). f. A large array (n=10).

Java Implementation

import java.util.*;

public class DescendingBubbleSort {
    // Performs Bubble Sort in descending order and counts swaps
    public int bubbleSortDescending(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]) { // Changed to < for descending order
                    // 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 descending Bubble Sort
    public static void main(String[] args) {
        DescendingBubbleSort sorter = new DescendingBubbleSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}),           // Unsorted, medium size
            new TestCase(new int[]{5, 4, 3, 2, 1}),                // Sorted (descending)
            new TestCase(new int[]{1, 2, 3, 4, 5}),                // Reversed (ascending)
            new TestCase(new int[]{3, 1, 3, 2, 1, 2}),             // Duplicates
            new TestCase(new int[]{}),                              // Empty
            new TestCase(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}) // Large, reversed
        };

        // 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.bubbleSortDescending(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: [64, 34, 25, 22, 12]
Swaps: 4

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

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

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

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

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

Explanation:

Test case 1: Unsorted array requires 4 swaps to sort in descending order.
Test case 2: Already sorted in descending order, 0 swaps.
Test case 3: Ascending array (reversed for descending) requires 10 swaps.
Test case 4: Array with duplicates requires 7 swaps.
Test case 5: Empty array requires 0 swaps.
Test case 6: Large array (n=10), already sorted in descending order, 0 swaps.

How It Works

bubbleSortDescending:
- Iterates through the array, comparing adjacent elements.
- Swaps if the first element is smaller (arr[j] < arr[j+1]), incrementing swaps.
- Each pass ensures the smallest 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] → [64, 34, 25, 22, 12] (1 swap: 12↔22).
- Pass 2: [64, 34, 25, 22, 12] → [64, 34, 25, 22, 12] (0 swaps).
- Pass 3: [64, 34, 25, 22, 12] → [64, 34, 25, 22, 12] (0 swaps).
- Pass 4: [64, 34, 25, 22, 12] → [64, 34, 25, 22, 12] (0 swaps).
- Pass 5: [64, 34, 25, 22, 12] → [64, 34, 25, 22, 12] (0 swaps). Total swaps: 4.
Main Method: Tests unsorted, sorted (descending), reversed (ascending), duplicates, empty, and large arrays.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
bubbleSortDescending	O(n²)	O(1)
toString	O(n)	O(n)

Note:

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

✅ Tip: Modify Bubble Sort for descending order by changing the comparison to arr[j] < arr[j+1]. Use a swap counter to analyze the algorithm’s performance across different inputs.

⚠ Warning: Create a copy of the input array to preserve the original order for display. Handle empty arrays to avoid index errors in the sorting loop.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners