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

Descending Insertion Sort

Problem Statement

Write a Java program that modifies the Insertion Sort implementation to sort an array of integers in descending order (largest to smallest) by adjusting the comparison logic. The program should count the number of shifts performed (the number of times elements are moved to make space for insertion) and test 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. Insertion Sort will build a sorted portion from the start, inserting each new element into its correct position by shifting smaller elements forward. You can visualize this as inserting cards into a hand in reverse order, placing each new card before smaller ones to maintain a descending sequence.

Input:

  • An array of integers to be sorted in descending order. Output: The sorted array (in descending order), the number of shifts 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]
    • Shifts: 6
  • Explanation: Insertion Sort inserts each element, shifting smaller ones, resulting in 6 shifts.
  • Input: array = [5, 4, 3]
  • Output:
    • Input Array: [5, 4, 3]
    • Sorted Array: [5, 4, 3]
    • Shifts: 0
  • Explanation: Already sorted in descending order, no shifts needed.

Pseudocode

FUNCTION insertionSortDescending(arr)
    SET n to length of arr
    CREATE shifts as integer, initialized to 0
    FOR i from 1 to n-1
        SET key to arr[i]
        SET j to i - 1
        WHILE j >= 0 AND arr[j] < key
            SET arr[j + 1] to arr[j]
            INCREMENT shifts
            DECREMENT j
        ENDWHILE
        SET arr[j + 1] to key
    ENDFOR
    RETURN shifts
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 shifts to insertionSortDescending(copy)
        PRINT input array, sorted array, and shifts
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define insertionSortDescending: a. Initialize a counter shifts to 0. b. For each index i from 1 to n-1:
    • Store arr[i] as key.
    • Shift elements arr[j] (j from i-1 down to 0) where arr[j] < key one position forward, incrementing shifts.
    • Insert key at the correct position. c. Return the number of shifts.
  2. Define toString: a. Convert the array to a string, e.g., "[64, 34, 25, 22, 12]".
  3. 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 DescendingInsertionSort {
    // Performs Insertion Sort in descending order and counts shifts
    public int insertionSortDescending(int[] arr) {
        int n = arr.length;
        int shifts = 0;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] < key) {
                arr[j + 1] = arr[j];
                shifts++;
                j--;
            }
            arr[j + 1] = key;
        }
        return shifts;
    }

    // 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 Insertion Sort
    public static void main(String[] args) {
        DescendingInsertionSort sorter = new DescendingInsertionSort();

        // 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 shifts = sorter.insertionSortDescending(arr);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Shifts: " + shifts + "\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]
Shifts: 6

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

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

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, ...]
Shifts: 163

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, ...]
Shifts: 62376

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

Explanation:

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

How It Works

  • insertionSortDescending:
    • Iterates from index 1 to n-1, treating arr[0..i-1] as sorted in descending order.
    • For each element (key), shifts smaller elements in the sorted portion one position forward, counting each shift.
    • Inserts the key in the correct position to maintain descending order.
  • 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):
    • i=1: key=34, no shift (34 < 64): [64, 34, 25, 12, 22].
    • i=2: key=25, no shift (25 < 34): [64, 34, 25, 12, 22].
    • i=3: key=12, shift 25, 34, 64: [64, 34, 25, 12, 22] (3 shifts).
    • i=4: key=22, shift 25: [64, 34, 22, 25, 12] (3 shifts).
    • Total shifts: 6.
  • Main Method: Tests small, medium, and large arrays with various contents.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
insertionSortDescendingO(n²) worst, O(n) bestO(1)
toStringO(n)O(n)
generateRandomArrayO(n)O(n)
generateSortedDescendingO(n)O(n)
generateDuplicatesArrayO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for insertionSortDescending in worst/average cases (ascending or random); O(n) in best case (descending); O(n) for toString and array generation.
  • Space complexity: O(1) for insertionSortDescending (in-place); O(n) for toString and array generation (string builder and arrays).
  • Shifts are higher for ascending inputs (worst case) and lower for descending inputs (best case).

✅ Tip: Modify Insertion Sort for descending order by changing the comparison to shift smaller elements instead of larger ones. Test with various array sizes to verify correctness across 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.