insertion sort in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs.

In this post, we will see how to implement insertion sort in java. Insertion sort is very much similar to bubble sort.

Insertion sort Algorithm

Insertion sort works by comparing values at index with all its prior elements.We place value at the index where there are no lesser value to the elements. So when you reach last element,we get a sorted array.
Lets see how it works:
Lets say you have array as {100,20,15,30,5,75}

  1. Compare 20 with 100,as 20 is less than 100, our array will become {100,100,15,30,5,75}. We have reached to 0th index, we will place 20 to 0th index {20,100,15,30,5,75}
  2. Compare 15 with 100, as it is less,our array will become {20,100,100,30,5,75}. Now compare 20 with 15, it is again less, our array will become {20,20,100,30,5,75}. As we have reached start of array again. Place 15 at 0th index.our array will become {15,20,100,30,5,75}
  3. Compare 30 with 100, as it is less,our array will become {15,20,100,100,5,75}.Now compare 30 with 20 again, it is more, so we will stop here, As we reached at index where 30 is greater than 15 and 20. so we will put 30 at this index. our array will become {15,20,30,100,5,75}
  4. Compare 5 with 100, as it is less, our array will become {15,20,30,100,100,75}. Now compare 30 with 5 again,it is less,our array will become {15,20,30,30,100,75}. Similarly 20 with 5, it is less,our array will become {15,20,20,30,100,75}.Compare 15 with 5, it is less,our array will become {15,15,20,30,100,75}.As we have reached start of array again. Place 5 at 0th index.our array will become {5,15,20,30,100,75}
  5. Compare 75 with 100, it is less,so our array will become {5,15,20,30,100,100}.Now compare 30 with 75 again, it is more, so we will stop here, As we reached at index where 75 is greater than 5,15,20 and 30. so we will put 75 at this index. our array will become {5,15,20,30,75,100}
  6. Finally we got sorted array.

Insertion sort implementation

I have printed intermediate steps to understand it better:

When you run above program, you will get following output:

We are iterating from first element to last element.You may notice that each iteration places current element at its right place where all its prior element are less than current element.

Time Complexity

Best case: O(n)
Average case: O(n^2)
Worst case: O(n^2)
To understand more about complexity,please go through complexity of algorithm.

That’s all about insertion sort in java.
Please go through java interview programs for more such programs.

Related Posts

  • 04 November

    Topological Sort in java

    Table of ContentsTopological Sort exampleTopological Sort AlgorithmWhy it works?Java program to implement topological sortingTime Complexity In this post, we will see about Topological Sorting in the graph. Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is […]

  • 23 August

    Sort array in java

    Table of ContentsJava Sort ArraySort Array of numbersSort Array of StringsSort array of custom objects In this post, we will see how to sort an array in java. There are various ways to sort array in java. You can implement different sorting algorithms to sort an array. You can use Arrays.sort method to sort array […]

  • 12 October

    Selection sort in java

    Table of ContentsSelection sort algorithmSelection sort algorithmTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs. Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs. Selection sort […]

  • 12 October

    Shell sort in java

    Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell. It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell […]

  • 12 October

    Quick Sort in java

    Table of ContentsQuick sort AlgorithmQuick Sort implementationTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions. Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm. In quick sort, we first choose a pivot and divide into two sublists,one […]

  • 12 October

    Counting Sort in java

    Table of ContentsSteps for Counting Sort:Java program for counting sort: Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times. Basic idea of counting sort to find number of elements […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.