DEV Community

Tanuja V
Tanuja V

Posted on • Updated on

Insertion Sort in Java (With Intuition + Dry run + Code)

Why the name insertion sort ?

The name "insertion sort" comes from the way this sorting algorithm works. It maintains a sorted sublist in the lower positions of the list. It iterates through the list, removing one element at a time and finding the correct position to insert it into the sorted sublist. This process continues until the whole list is sorted. The term "insertion" refers to the action of inserting an element into its correct position within the sorted sublist.

Algorithm :

  1. Start with the second element (index 1) of the array.
  2. Compare this element to the one before it. If the previous element is greater, swap the two elements.
  3. Continue comparing the element to the ones before it and swapping as needed until the element is in its correct sorted position.
  4. Move to the next element (index 2) and repeat steps 2-3 until the entire array is sorted.

I will show the working of Insertion sort but make sure to dry run using pen & paperπŸ“

insertion-sort1

insertion-sort2

insertion-sort3

insertion-sort4

Code


 java
public class InsertionSort {
    public static void main(String[] args) {
       // int arr[] = {5, 4, 10, 1, 6, 2};
        int arr[] = {12, 11, 13, 5, 6};
        int n = arr.length;

        for(int i=1; i<n; i++){
            int temp = arr[i];
            int j = i-1;

            while(j>=0 && arr[j]>temp){
                arr[j+1] = arr[j];
                j--;
            }

            arr[j+1] = temp;
        }

        for(int i=0; i<n; i++){
            System.out.print(arr[i]+" ");
        }
    }
}


Enter fullscreen mode Exit fullscreen mode

Time Complexity:

  • Best Case: O(n)
  • Worst Case: O(n^2)

Space Complexity:

O(1)

Wrapping Up:

Now, congrats, you've learned insertion sort πŸ₯³πŸ‘
Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🀝 && Happy Coding πŸš€

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Top comments (2)

Collapse
 
sehgalspandan profile image
Spandan Sehgal

Well explained!

Collapse
 
tanujav profile image
Tanuja V

Thank you, Spandan