**Part 4 : Insertion Sort**

Part 2 : Bubble Sort

Part 3 : Selection Sort

Sorting again,

Sorry to disapoint but i had no choice because this sorting also uses the Array data structure so doing it straightaway is better than comming back later. So let's see about the insertion sort, again a not-so-good sorting with some of uses of its kind and move onto a whole new brand of algorithms.

**Insertion Sort**

Like most of the sorting algorithms, this too has the core concept of "swapping: but instead of saving the swaps like in the Selection Sort, this algorithm concerns more about saving the times which the inner loops will run, saving us some valuable CPU calls at the same time dedicating swaps. however the algorthims is know the be really efficient for part sorted, or almost sorted arrays or sequence in which the time taken for sorting would decrease drastically when compared to other Bubble Sort and Selection Sort which have a const time for the sorting in most of the cases.

__How Insertion Sort works?__

Image from wiki article |

ex: Sort an array of numbers using Insertion Sort

{5,6,2,3,4} We start off with the second element that is, 5

{6,5,2,3,4} We start by backtracking from the element before the selected, that is 6. The condition for the backtracking to end is that either the item being backtracked [compared to the selected element] is lower than the selected or the start of the array is reached [that is the index no of the backtrack is 0]

{5,6,2,3,4} As 6 > 5 and 6's index no is 1, the swap is done between 5 & 6. Still the backtracking hasnt ended.

{5,6,2,3,4} We check what's the one before 5 now, ah it is the start if the array, now we can safely put the END IT signal and goto the next element, that is third [index no. 2], 2.

{5,2,6,3,4} When 2 is compared with 6, as 6 > 2 they are swapped

{2,5,6,3,4} When 2 is compared with 5, as 5 > 2, they are swapped

{2,5,6,3,4} Ouch! the start of the array, so the loop ends.

Like wise it goes till the last element is processed like this.

{2,3,4,5,6} We get this after all, BIG DEAL! :D

__Pseudo-code__

- S : sequence of sortable items
- N : no of items
- for i = 1 to N-1 do
- j = i-1;
- temp = S[i];
- while j>=0 and S[j] > temp
- S[j+1] = S[j];
- j = j-1;
- end while
- S[j+1] = temp;
- end for

__Explanation__

First we take

**S**, the sequence of sortable, comparable items, in this case an array of integers.

**N**, no. of elements.

__Line 4:__we take the main loop, starting to proccess from the second element onwards. Why second element is need to backtrack and if we start with first element we have no chance of backtracking as it is the start :D

__Line 5:__We take j as the starting point of backtracking, we dont need to compare with the current item so we start with item one behind the current

__Line 6:__For future use, the current element is saved to a temp variable

__Line 8:__THE MOST IMPORTANT, we start the backtracking, the conditions are vital it to be successful, we search backwards till either the searched item is less than the current [so that obviously the the current should come after the searched] or the we reach the start of the array.

__Line 9-10:__Swapping and then reducing the value of

**j**.

__Line 13:__At the end of each loop we need to remember on thing, now our selected element has no place as it was swapped to one behind in the process, so the variable j holds ONE ELEMENT BEFORE THE EXACT place where the current one should actually be. Why one before is that an additional

**j-1**is executed due to the way while loop works. [no way i'm explaining that as well]. So at the end of the main loop, we put the current element to rightly chosen place, the sorted place.

Ahh lets get to the geek part ;)

__Insertion Sort Implementation in C++__

__Insertion Sort Implementation in Java__

*Output : 10 20 30 40 50 65*__Efficiency of Insertion Sort__

For this one, i have very little to talk,as the algorithm it self is more likely the other two, meaning they give the usual

*n^2*in worst cases. But remember that if this is a sorted array we are trying to sort, while all the other two will run more than

*n*time, this will run smoothly only in n time and end, and for that only we can give the credit :)

Worst Case: O(

*n*

^{2})

Average Case: O(

*n*

^{2})

Best Case: O(

*n*)

Now, i'm serious this time that the next WONT be another sorting, and well you have put the array into some good use, may be need something with more power next time.

Wait for it :D

## No comments:

## Post a Comment