Insertion Sort in Ascending Order in Java

Author:

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. Insertion sort works similarly as we sort cards in our hands in a card game. 

In this blog post, we will deep dive into the mechanism of Insertion Sort, followed by its implementation in Java to sort an array in ascending order. 

Java Program for Insertion Sort in Ascending Order:

public class InsertionSortAscending {

    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 ascending order:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }

    /**
     * Sort an array using the insertion sort algorithm.
     *
     * @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 ascending order:
-22 -15 1 7 20 35 55

Step-by-Step Explanation: 

Initialization: We initiate a sample integer array named numbers that we wish to sort in ascending order. 

The Core Idea: The primary notion behind Insertion Sort is the division of the array into two sections – sorted and unsorted. Initially, the sorted section contains just the first element, and with each iteration, elements from the unsorted section are 'picked' and then 'inserted' into their correct position in the sorted section. 

Looping through the Array: The insertionSort method carries out the sorting. For every iteration (starting from the second element), we assume that this element might be out of order and might need insertion in the previously sorted section. 

Finding the Right Position: By iterating backward from the current element, we make room by shifting elements to the right until we find the correct position to insert our element. 

Inserting the Element: Once the right position is identified, the current element (from the unsorted section) is placed in its rightful position in the sorted section. 

Displaying Sorted Array: Post the completion of sorting; the sorted numbers array is displayed element by element. 

The beauty of Insertion Sort lies in its simplicity. However, it might not be the best choice for large datasets due to its O(n^2) average time complexity. Still, for small datasets, it often outperforms other complex algorithms. And now, with this step-by-step guide, you should be adept in implementing Insertion Sort in Java for ascending order sorting. Happy coding!

Comments

Post a Comment

Leave Comment