**Insert an element into the sorted array**

The key to understand insertion sort is to first write a simple function that would insert an element into a given array that is already sorted. There are a couple of assumptions we are going to make here, to make the job easy.

- Assume that the array has space to insert one more element i.e there is an additional empty space at the end of the array (There is no need to resize the array to add space for the new element)
- The elements in the array are already sorted, so we need to insert the new element in the right place or index of the array.

- Pick the last element in the array i.e the element before the empty slot.
- Compare the above array element with the new element we want to insert.
- If the array element is larger than the new element - We move the array element to a higher memory address or array index.
- We repeat the above process till we hit a condition where the new element is larger than array element.
- In this case we insert the new element in the current index/free slot of the array.

**Step 1 :**Free slot is at the end of the array,**Step 2 :**Now we pick the next element which is 7, since 7 is larger than 4, we move 7 to next higher index, now free slot is two levels below the last element.**Step 3 :**Now we pick the next element which is 6, since 6 is larger than 4, we move 6 to next higher index, now free slot is three levels below the last element.**Step 4 :**Now we pick the next element which is 3, since 3 is less than 4, we insert 4 in the current index.

void sampleInsert(int array[], int value) { // Assuming last item is empty int reverseIndex = array.length - 1; //start the loop from second last element since last is empty for (int i = array.length - 2; i >= 0; i--) { //If the array element is greater than the value //move the array element to the next higher index if (array[i] >= value) { array[i + 1] = array[i]; reverseIndex = i; } else { break; } } array[reverseIndex] = value; }

Now that we have understood the insert routine/method, lets look at insertion sort algorithm itself.

**Insertion Sort algorithm**

Here is how insertion sort is often explained, it works the way you might sort a hand of playing cards

- We start with an empty sorted array ( this means our array is full of unsorted elements )
- Then remove one element at a time from the unsorted array, and insert it into the correct position in the sorted array.
- To find the correct position for the element, we use the above sample code.

**Code**

Now lets try to code implement insertion sort algorithm in the simplest possible way as explained above.

public void sort(int array[]) { //Ignore the first array element [0] since array with one element is always sorted //start from the array [1] -- Get that element and insert for (int index = 1; index < array.length; index++) { insert(array, index); } }Done, that's it. All we are doing in the above code is take/read each element in the unsorted array and inserting that element back into the array which does the sort.

As you can see the algorithm can be implemented in few lines, easy to remember once you know how to implement insert routine.

Here is the the insert routine/method, same code as above sampleInsert() - The difference is, rather than taking a value to insert, it takes the index of value to insert.

void insert(int array[], int currentIndex) { //value of the element to be inserted int value = array[currentIndex]; //iterate in the loop for all elements below the currentIndex int reverseIndex = currentIndex; for (int i = currentIndex - 1; i >= 0; i--) { //If the array element is greater than the value //move the array element to the next higher index if (array[i] >= value) { array[i + 1] = array[i]; reverseIndex = i; } else { break; } } array[reverseIndex] = value; }

**What is the complexity of the above algorithm ?**

**Average and Worst Case:**

Its

**O(n**- Since there is a nested loop.

^{2})

**Why ?**

There is loop in the above sort() method, which calls insert(), which again has a loop. Hence a nested loop.

**Best case :**

Now lets consider the best case. What if the array is already sorted and we do a insertion sort on this ?. This means we need to insert element only at the end of the array. So the inner for loop never gets executed. So best case is

**O(n).**

**Space Complexity**is none since we did not allot any new arrays.

Check the other article on How to find the complexity of a code and rest of the articles here.

**Source code**

Here is the complete insertion sort sample java file used in this post.

## No comments:

## Post a Comment