Implement Insertion Sort using Java

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are specific approaches to solve problems in such a way that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some basic programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Insertion Sort using Java.

 

What is Insertion Sort?

 

• Comes in the list of simplest data structure, Insertion Sort is the way of arranging elements in ascending order. The array is either sorted or is unsorted.

 

• When the array is sorted this data structure works quickest. However, when elements aren’t sorted it works the slowest.

 

What’s The Approach?

 

• Consider arr[n] of size n we want to implement Insertion Sort on. So firstly we’ll iterate a loop from 1 to n.

 

• Next, we’ll compare the element at iterating index with its preceding element from the array. If the comparing element is smaller, we’ll again compare it with the before elements.

 

• Lastly, Move the greater elements one position up to make space for the swapped element.

 

Also Read: Implement Linked List using Java

 

Java Program To Implement Insertion Sort

 

Input:

 

12, 11, 13, 5, 6

 

Output:

 

5 6 11 12 13

 

// Java program for implementation of Insertion Sort
class TechDecodeTutorials {
    /*Function to sort array using insertion sort*/
    void sort(int arr[])
    {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
            greater than key, to one position ahead
            of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    /* A utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");

        System.out.println();
    }

    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6 };

        TechDecodeTutorials TDT = new TechDecodeTutorials();
        TDT.sort(arr);

        printArray(arr);
    }
}