Insertion Sort in Descending Order in Java

Author:

Insertion sort is an elementary and intuitive sorting algorithm that's efficient for relatively small datasets. It's analogous to the process of sorting playing cards in one's hands. While ascending order is more common, you might sometimes need to sort data in descending order. In this article, we'll walk you through the mechanism of Insertion Sort and how to use it to sort an array in descending order in Java. 

Java Program for Insertion Sort in Descending Order

public class InsertionSortDescending {

    public static void main(String[] args) {
        // Sample array of numbers to be sorted
        int[] numbers = {20, 35, -15, 7, 55, 1, -22};

        // Sort the array using Insertion Sort
        insertionSort(numbers);

        // Display the sorted array
        System.out.println("Sorted array in descending order:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }

    /**
     * Sort an array using the insertion sort algorithm in descending order.
     *
     * @param arr The array to be sorted.
     */
    public static void insertionSort(int[] arr) {
        for (int firstUnsortedIndex = 1; firstUnsortedIndex < arr.length; firstUnsortedIndex++) {
            int newElement = arr[firstUnsortedIndex];
            int i;

            // Compare the new element to elements in the sorted section of the array
            for (i = firstUnsortedIndex; i > 0 && arr[i - 1] < newElement; i--) {
                arr[i] = arr[i - 1];
            }

            // Insert the newElement into its appropriate position
            arr[i] = newElement;
        }
    }
}

Output: 

Sorted array in descending order:
55 35 20 7 1 -15 -22

Step-by-Step Explanation: 

Initialization: We begin with a sample integer array named numbers that we aim to sort in descending order. 

Concept: The heart of Insertion Sort is that it segments the array into two parts: sorted and unsorted. Initially, the sorted segment has only one element. With each loop iteration, we 'pick' an element from the unsorted segment and 'insert' it at the right position within the sorted section. 

Looping through the Array: The actual sorting happens inside the insertionSort function. For each pass (starting from the second element), we consider the element may be out of place and might need repositioning within the already sorted section. 

Identifying the Correct Position: By moving backward from the current element's position, we make space for it by shifting elements to the left until we locate the suitable position to place it. Note that, for descending order, the comparison is reversed (arr[i - 1] < newElement). 

Positioning the Element: The current element (from the unsorted section) is then placed in the located position, ensuring the sorted segment remains sorted but now includes one more element. 

Display: Once sorted, the array is displayed to the console. 

Insertion sort shines with its simplicity and its efficiency for small datasets. Even though it's not optimal for very large datasets due to its O(n^2) average time complexity, for small datasets, it can outperform many advanced sorting algorithms. With this guide, you should be well-equipped to implement the Insertion Sort in Java for descending order sorting. Happy coding!

Comments

Post a Comment

Leave Comment