- The principle of insertion sort is quite simple.Each successive element in the array to be sorted and inserted into its proper place with respect to the other already sorted element.
- Every repetition of insertion sort,removes an element from the input data & inserting into correct position in the already sorted list,until no input elements remain.
We take an unsorted array for our example.
Insertion sort compares the first two elements.
Both 22 and 79 are already in ascending order.now, 22 is in sorted sub_list.
Insertion sort moves ahead and compares 79 and 45.
79 is not in the correct position.it swaps 79 with 45.It also checks with all the elements of sorted sub_list.Here we see that the sorted sub_list has only one element 22,and 45 is greater than 14.so don't need to chance 22.
Next it compares 79 with 8.
These values are not in a sorted order.swap them too,
Swapping makes 45 and 8 unsorted.
Hence,swap them too.
Again swapping makes 22 and 8 unsorted.
Hence swap them too,
Next we compare 79 with 32.
79 is greater than 32 .so swap 79 and 32
Now, swapping makes 45 and 32 unsorted
Swap 45 and 32,now we have sorted sub_list of 4 items.
Now,we have 79 and 56.79 is greater than 56.
Finally swap 79 and 56 we get sorted sub_list.
Efficiency of Insertion sort:
Assume that an array containing 'n' elements is sorted using insertion sort technique.
- The minimum no.of elements that must be scanned=n-1
- For each of the elements the max.no.of shifts possible=1
Advantages:
- It is one of the simplest sorting techniques that is easy to implement.
- It performs well in case of smaller list.
- It leverages the presence of any existing sort pattern in the list thus resulting in better efficiency.
Disadvantages;
- The efficiency of O(n^2) is not well situated for large sized lists.
- It requires large number of elements to be shifted.
No comments:
Post a Comment