Descending Selection Sort

Problem Statement

Write a Java program that modifies the Selection Sort implementation to sort an array of integers in descending order (largest to smallest) by selecting the maximum element in each pass instead of the minimum. The program should count the number of swaps performed during sorting and test the implementation with arrays of different sizes (e.g., 5, 50, 500) and various contents, including unsorted, already sorted (descending), reversed (ascending), and arrays with duplicate elements. Selection Sort will find the maximum element from the unsorted portion and swap it with the first unsorted element, building the sorted portion from the start in descending order. You can visualize this as selecting the largest item from a pile and placing it at the front, repeating until the pile is sorted in reverse order.

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: 3
Explanation: Selection Sort finds the maximum in each pass, swapping it to the front, resulting in 3 swaps.
Input: array = [5, 4, 3]
Output:
- Input Array: [5, 4, 3]
- Sorted Array: [5, 4, 3]
- Swaps: 0
Explanation: Already sorted in descending order, no swaps needed.

Pseudocode

FUNCTION selectionSortDescending(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET maxIdx to i
        FOR j from i+1 to n-1
            IF arr[j] > arr[maxIdx] THEN
                SET maxIdx to j
            ENDIF
        ENDFOR
        IF maxIdx != i THEN
            SET temp to arr[i]
            SET arr[i] to arr[maxIdx]
            SET arr[maxIdx] to temp
            INCREMENT swaps
        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 with different sizes
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET swaps to selectionSortDescending(copy)
        PRINT input array, sorted array, and swaps
    ENDFOR
ENDFUNCTION

Algorithm Steps

Define selectionSortDescending: a. Initialize a counter swaps to 0. b. For each index i from 0 to n-1:
- Find the maximum element’s index maxIdx in arr[i..n-1].
- If maxIdx != i, swap arr[i] with arr[maxIdx] and increment swaps. 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. Small unsorted array (n=5). b. Small sorted array (descending, n=5). c. Small reversed array (ascending, n=5). d. Medium array with duplicates (n=50). e. Large unsorted array (n=500). f. Empty array (n=0).

Java Implementation

import java.util.*;

public class DescendingSelectionSort {
    // Performs Selection Sort in descending order and counts swaps
    public int selectionSortDescending(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIdx]) {
                    maxIdx = j;
                }
            }
            if (maxIdx != i) {
                // Swap elements
                int temp = arr[i];
                arr[i] = arr[maxIdx];
                arr[maxIdx] = temp;
                swaps++;
            }
        }
        return swaps;
    }

    // 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();
    }

    // Generates random array for testing
    private int[] generateRandomArray(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] = rand.nextInt(2001) - 1000; // [-1000, 1000]
        }
        return arr;
    }

    // Generates sorted array (descending) for testing
    private int[] generateSortedDescending(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }
        return arr;
    }

    // Generates array with duplicates
    private int[] generateDuplicatesArray(int n) {
        Random rand = new Random(42);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(10); // Limited range for duplicates
        }
        return arr;
    }

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

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

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

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}, "Small unsorted (n=5)"),
            new TestCase(sorter.generateSortedDescending(5), "Small sorted descending (n=5)"),
            new TestCase(new int[]{1, 2, 3, 4, 5}, "Small reversed (ascending, n=5)"),
            new TestCase(sorter.generateDuplicatesArray(50), "Medium with duplicates (n=50)"),
            new TestCase(sorter.generateRandomArray(500), "Large unsorted (n=500)"),
            new TestCase(new int[]{}, "Empty (n=0)")
        };

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

Output

Running the main method produces:

Test case 1: Small unsorted (n=5)
Input Array: [64, 34, 25, 12, 22]
Sorted Array: [64, 34, 25, 22, 12]
Swaps: 3

Test case 2: Small sorted descending (n=5)
Input Array: [5, 4, 3, 2, 1]
Sorted Array: [5, 4, 3, 2, 1]
Swaps: 0

Test case 3: Small reversed (ascending, n=5)
Input Array: [1, 2, 3, 4, 5]
Sorted Array: [5, 4, 3, 2, 1]
Swaps: 4

Test case 4: Medium with duplicates (n=50)
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Sorted Array: [9, 9, 9, 9, 8, 8, 8, 8, 8, 8, ...]
Swaps: 40

Test case 5: Large unsorted (n=500)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Sorted Array: [976, 966, 964, 960, 958, 955, 953, 952, 951, 946, ...]
Swaps: 492

Test case 6: Empty (n=0)
Input Array: []
Sorted Array: []
Swaps: 0

Explanation:

Test case 1: Unsorted array (n=5) requires 3 swaps to sort in descending order.
Test case 2: Already sorted in descending order (n=5), 0 swaps.
Test case 3: Ascending array (reversed for descending, n=5) requires 4 swaps.
Test case 4: Medium array with duplicates (n=50) requires 40 swaps.
Test case 5: Large unsorted array (n=500) requires 492 swaps.
Test case 6: Empty array (n=0) requires 0 swaps.

How It Works

selectionSortDescending:
- Iterates through the array, finding the maximum element in the unsorted portion.
- Swaps the maximum with the first unsorted element if needed, incrementing swaps.
- Builds the sorted portion in descending order from the start.
toString: Formats array as a string, limiting output to 10 elements for large arrays.
generateRandomArray: Creates an array with random integers in [-1000, 1000].
generateSortedDescending: Creates a descending array [n, n-1, ..., 1].
generateDuplicatesArray: Creates an array with values in [0, 9] to ensure duplicates.
Example Trace (Test case 1):
- Pass 1: Find max=64 at index 0, no swap: [64, 34, 25, 12, 22].
- Pass 2: Find max=34 at index 1, no swap: [64, 34, 25, 12, 22].
- Pass 3: Find max=25 at index 2, no swap: [64, 34, 25, 12, 22].
- Pass 4: Find max=22 at index 4, swap with 12: [64, 34, 25, 22, 12] (1 swap).
- Pass 5: Find max=12, no swap. Total swaps: 3.
Main Method: Tests small, medium, and large arrays with various contents.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
selectionSortDescending	O(n²)	O(1)
toString	O(n)	O(n)
generateRandomArray	O(n)	O(n)
generateSortedDescending	O(n)	O(n)
generateDuplicatesArray	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(n²) for selectionSortDescending (n passes, up to n comparisons each); O(n) for toString and array generation.
Space complexity: O(1) for selectionSortDescending (in-place); O(n) for toString and array generation (string builder and arrays).
Selection Sort always performs O(n²) comparisons, with swaps O(n) in the worst case.

✅ Tip: Modify Selection Sort for descending order by selecting the maximum element instead of the minimum. Test with various array sizes to ensure robustness across small and large 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