International Journal of Computer Applications (0975 – 8887)

Volume 64– No.21, February 2013

Enhanced Insertion Sort Algorithm

Tarundeep Singh Sodhi Surmeet Kaur Snehdeep Kaur

Assistant Professor in CSE Assistant Professor in CSE dept. at Student of MCA at Guru Nanak
dept. at ARNI University, Lovely Professional University, Dev University, Regional
Kathgarh Indora-H.P. Jalandhar. campus, jalandhar.
B-5 B-5
H.No /108, Ganga Singh Nagar H.No-170A , 2 Partap Nagar, H.No /108, Ganga Singh Nagar
Jandiala road,Tarn-Taran. Opposite Kamal Palace, Sangrur. Jandiala road,Tarn-Taran.
Pincode-143401 Pincode-148001 Pincode-143401

ABSTRACT  The output is a permutation, or reordering,


Sorting is integral part of many computer based systems of the input. \
and applications, as it involves rearranging information The output is in non decreasing order.
into either ascending or descending order. There are
many sorting algorithms like Quick sort, Heap sort, Merge Many researchers considered all sorting techniques had
sort, Insertion sort, Selection sort, Bubble sort and been discovered, but many useful new sorting
Freezing sort. However, efforts have been made to algorithms are recently introduced, for example, library
improve the performance of the algorithm in terms of sort was first published in 2004.
efficiency, indeed a big issue to be considered. Major
Emphasis has been placed on complexity by reducing the
Insertion sorting algorithm is another important
Number of comparisons, hence reducing complexity. This
algorithm, used for sorting small lists. But the study
paper presents new sorting algorithm EIS, “ENHANCED
shows that the EIS is more efficient, theoretically,
INSERTION SORT”.It is basically an enhancement
analytically, and practically as compared to the original
toINSERTION SORT (a kind of Hybrid sorting
(insertion) sorting algorithm and also good for sorting
technique) by making it impressively faster algorithm with
bigger lists. Section III presents the concept of EIS
O(n)complexity as compared to O(n2) of insertion sort in
algorithm and its pseudo code. Furthermore, the
worst case and less than O(n1.585) in average case which is
implementation, analysis, and comparison with insertion
much better than insertion sort O(n2). It works flawlessly
sort and other algorithms are highlighted.
with huge lists of elements. To prove the effectiveness of
the algorithm, the new algorithm is analyzed, implemented,
tested and results has been carried out and compared with 2. ABOUT INSERTION SORT
other major sorting algorithms and the results were The insertion sort, as its name suggests, inserts each
promising. item into its proper place in the final list. The simplest
implementation of this requires two list structures: the
General Terms source list and the list into which sorted items are
Sorting Algorithm, Hybrid technique, EIS-Enhanced
inserted.
Insertion sort, NOC- Number of Comparisons, NOE-
Number of elements. 2.1 Example
45 30 60 25 70 20 80 75 15 10
Keywords 30 45 60 25 70 20 80 75 15 10
Enhanced Insertion sort, EIS, NOC, NOE, Freezing Sort, 30 45 60 25 70 20 80 75 15 10
complexity, selection sort, bubble sort, transition element. 25 30 45 60 70 20 80 75 15 10
25 30 45 60 70 20 80 75 15 10
1. INTRODUCTION 20 25 30 45 60 70 80 75 15 10
Algorithm is a stepwise method to solve a problem, 20 25 30 45 60 70 80 75 15 10
20 25 30 45 60 70 75 80 15 10
efficiently and expressed as a finite sequence of steps. 15 20 25 30 45 60 70 75 80 10
Algorithms are used for calculation, data processing, and 10 15 20 25 30 45 60 70 75 80
many other fields.
 Calculating the number of green elements, we can
Sorting has been considered as a fundamental observe that no of comparisons in all are 31.


problem in the study of algorithms, that due to


many reasons: Red elements show the transitioned elements
The need to sort information is inherent in
many applications.
 Algorithms often use sorting as a key subroutine
3. ENHANCED INSERTION SORT
and efficient sorting is important to optimize
the use of other algorithms that require sorted 3.1 Concept
lists to work correctly. Inserting a new element at desired place in already sorted
part of an and decreasing the number of comparisons of
The output should satisfy two major conditions: the array by one for next call. In fact, the Enhanced

35
 International Journal of Computer Applications (0975 – 8887)
Volume 64– No.21, February 2013

Insertion Sort(EIS) algorithm is an enhancement to the IS 8. else i++ and repeat-3

algorithm, but the difference is in the approach as it 9. end if
compares with the very first element i.e.A[0] in the sorted 10. if (a[i]<a[j]), then goto-16
part of array, which in fact is the smallest element in the 11. elseif (if (a[i] = = a[j]), then
th th 12. set j = j+1 and goto-35
list at instant , after comparing i element with (i-1) .
This is called as hit method; more we get hit more the 13. end if
efficiency increases. 14. else goto-25
15. end if
Basically sometimes we have element which gets sorted 16. while((j-1)>=0), do
after (n-1) comparisons i.e at first place A[0] in insertion 17. j = j-2 and if (a[i]>a[j]), then
sort. So for reducing these useless comparison, why not 18. if (a[i] < a [j+1]), then
we compare the element to be sorted with the very first 19. set j = j+1 and goto-35
element A[0] in the part of list, which is already sorted i.e. 20. else set j = j+2 and goto-35
th 21. end if
before i element, which we know is the smallest element
22. else if (a[i] = =a[j]), then
up till now.
23. Set j = j+1 and goto-35
24. Else return
Further list is divided, selecting a middle element and
25. While (((i-1)-j) > = 0 ), do
comparing to part on its left or right based on the condition
26. J = j+2 and (a[i] < a[j]), then
for middle comparison and then comparing after leaving
one element in that particular part, hence reducing the no 27. If (a[i] < a [j-1]), then
of comparisons. The technique is more efficiently suitable 28. Set j=j-1 and goto-35
th 29. Else set j+j+0 and goto-35
for bigger lists and efficiency increases when the i is 30. End if
less than A[0] which gives O[n] in worst case. 31. Else if (a[i]= = a[j]), then
32. Set j=j+1 and goto-35
33. Else return
3.2 Procedure 34. End if
The whole procedure which shows the enhancement in 35. Swap a[i] and a[j]
the insertion sort technique as described below:- 36. j++
37. while(j=i-1), do
38. i++ and goto-3
1. Instead of comparing all the elements from right
39. END
to left, we just compare the ith element with
(i-1)th element.
2. If ith > (i-1)th then the element is simply
added/appended to the list i.e no swapping. 3.4 Analysis and Comparisons
Else EIS algorithm is easy to analyze as compared to IS
3. Compare ith element with ptr, (i.e. first element algorithm since the loop does not requires scanning
which is smallest in current sorted list) as the all i-1 elements (this takes i-1 comparisons) and
elements from A[0]th to A[i-1]th are already th
sorted. then swapping the i element into its appropriate
4. If ith <ptr then insert ith element before ptr and position as in IS algorithm.
ptr to this element. (which is now smallest and
first element in the list )a n d s w a p further list
accordingly. Else 3.4.1. Swaps
5. If the element lies between A[0]th and the (i-1)th We can very well observe that there is no change in
element, then we further divide the total number number of swaps in this technique as compared to
of sorted elements or ith by 2 i.e k = (i-1)/2 or insertion sort as the previous list is already sorted in both
k=i/2. We take the later one. the techniques and we just have to find the place for the
6. Now compare the ith element with kth element next element. For example:
and check again. For 10 Elements


7. If ith < kth, then compare with k-2 and so on until 5,60,37,28,50,20,160,7,89,10


we find an element kth < ith and then compare Number of swaps in Insertion sort 22
with (k+1)th and swap based on conditions. Number of Swaps in Enhanced insertion sort
8. If ith > kth then compare with k+2 and so on until 22
we find an element kth > ith and then compare
with (k-1)th and swap ith based on condition 2. 3.4.2. Complexity

3.3 Pseudo code 3.4.2.1. Best Case

1. Calculate length n In the best case, when all the elements in the array are in
2. var i=1,j
increasing order, then there should be no comparisons
3. if (a[i] < a [i-1]), then
for i=1, 2, 3……..n. So we get the running time in
4. if (a[i] < a [0]), then
5. set j = 0 and goto-35 linear order i.e O(n) which is same as that of insertion sort.
6. else j = i/2 and goto-10
7. end if

36
 International Journal of Computer Applications (0975 – 8887)
Volume 64– No.21, February 2013

3.4.2.2. Average Case

The average case of enhanced insertion sort is also For example, consider the list of 106 elements as below,
quadratic as is the case with insertion sort when we have where we have maximum number of comparisons when
an unsorted array, but it reduces the number of comparison sorted with EIS:
as compared to insertion sort, as it is observed that the 950,50,750,250,751,249,752,248,753,247,754,246,755,245
average case of insertion sort can often be as bad as worst ,756,244,757,243,758,242,759,241,760,240,761,239,762,2
case i.e there may be a need to compare each element A[i] 38,763,237,764,236,765,235,766,234,767,233,768,232,769
with each elements in the entire sorted sub array ,231,770,230,771,229,772,228,773,227,774,226,775,225,7
A[1],A[2],…….A[i-1] and thus the time can be expressed 76,224,777,223,778,222,779,221,780,220,781,219,782,218
as a quadratic equation i.e O( n2 ), but this is never the ,781,217,782,216,783,215,784, 214,785, 213,786, 212,787,
case with any unsorted array in EIS. 211,788,210,789,209,790,208,791,207,792,206,793,794,20
5,795,204,796,203,797,202,798,201,799,200,800
th Let us include them one by one.(Green shows the element
So in an unsorted array, when the i element to be
th th to be compared, red represent the current element which is
sorted lies at A[2] or A[i-2] position we being added and brackets represents the number of times it
have maximum number of comparisons which is much is compared)
less than the worst case of insertion sort.

Table 1: LISTING

LIST NUMBER 950,50,750,250,751,249,752, 248,753, 247,754, 246,755,245,756,

INPUT OF 244,757,243,758,242,759,241,760,240,761,239,762,238,763,237,
Elements 764,236,765, 235,766, 234,767, 233,768, 232,769, 231,770, 230,771,
(NOE) = 229,772,228,773,227,774,226,775, 225,776, 224,777, 223,778, 222,
106 779, 221,780,220,781,219,782, 218,781, 217,782, 216,783, 215,784,
214,785, 213,786, 212,787, 211,788, 210,789, 209,790, 208,791,207,
792,206,793,794,205,795,204,796,203,797,202,798,201,799,200,800

VALUE OF NOE ETI NOC ( NMPC )

(i) (Sorted List) Element LIST AFTER SORTING Number Number of
To Of Possible
INSERT Compari Comparisons
sons
i=1 0 50 50,950 1 1
i =2 2 750 50,750,950 2 3
i =3 3 250 50,250,750,950 3 4
i =4 4 751 50,250,750,751,950 3 4
i =5 5 249 50,249,250,750,751,950 4 5
i =6 6 752 50,249,250,750,751,752,950 4 5
i =7 7 248 50,248,249,250,750,751,752,950 4 5
i =8 8 753 50,248,249,250,750,751,752,753,950 4 5
i =9 9 247 50,247,248,249,250,750,751,752,753,950 5 6
i =10 10 754 50,247,248,249,250,750,751,752,753,754,950 5 6
i =11 11 246 50,246,247,248,249,250,750,751,752,753,754,950 5 6
i =12 12 755 50,246,247,248,249,250,750,751,752,753,754,755,950 5 6
i =13 13 245 50,245,246,247,248,249,250,750,751,752,753,754,755, 6 7
950
i =14 14 756 50,245,246,247,248,249,250,750,751,752,753,754,755, 6 7
756,950
i =15 15 244 50,244,245,246,247,248,249,250,750,751,752,753,754, 6 7
755,756,950
i =16 16 757 50,244,245,246,247,248,249,250,750,751,752,753,754, 6 7
755,756,757,950
i =17 17 243 50,243,244,245,246,247,248,249,250,750,751,752,753, 7 8
754,755,756,757,950
i =18 18 758 50,243,244,245,246,247,248,249,250,750,751,752,753, 7 8
754,755,756,757,758,950
i =19 19 242 50,242,243,244,245,246,247,248,249,250,750,751,752, 7 8
753,754,755,756,757,758,950

i =20 20 759 50,242,243,244,245,246,247,248,249,250,750,751,752, 7 8

753,754,755,756,757,758,759,950
i =21 21 241 50,241,242,243,244,245,246,247,248,249,250,750,751, 8 9

37
 International Journal of Computer Applications (0975 – 8887)
Volume 64– No.21, February 2013

752,753,754,755,756,757,758,759,950
i =22 22 760 50,241,242,243,244,245,246,247,248,249,250,750,751, 8 9
752,753,754,755,756,757,758,759,760,950
i =23 23 240 50,240,241,242,243,244,245,246,247,248,249,250,750, 8 9
751,752,753,754,755,756,757,758,759,760,950
i =24 24 761 50,240,241,242,243,243,245,246,247,249,250,750,751, 8 9
752,753,754,755,756,757,758,759,760,761,950

And so on….So to arrange any nth element in the list, Here as compared to insertion sort there are only 16
number of comparisons required are ┌n/4┐+12.
So as we can notice, after n=4 we have 4 times the same So there is always reduction in no of comparisons.
number of comparisons starting from 5,6,7……so on. So
talking about n=48, no of comparisons will be 3.4.4 Pseudo code
Insertion sort works by removing an element from the
15+15+15+15+14+14+14+14+13+13+13……….=449
input data for every repetition of insertion sort, inserting
it into the correct position in the already sorted list, until
The number of comparisons as calculated are always less no input elements remain. The insertion sort has a
than n1.585. So the complexity in the worst scenario of 2
complexity of O(n ). In simple pseudo code, insertion
average case will be O(n 1. 585) for constant 1. sort algorithm might be expressed as:
The complexity may vary from O(n) to O(n1. 585)
For example….for n=48,the number of comparisons 1. for j ←1 to length (A)-1
calculated manually are 449 which is less than 481.585 i.e 2. key ← A [ j ]
462. 3. > A[j] is added in the sorted sequence A
3.4.2.3 Worst Case [1... j-1]
In the worst case of Insertion Sort , when the array 4. i ← j - 1
is in decreasing order, one must compare each 5. while i >= 0 and A [i] > key
element A[i] with each elements in the entire sorted sub 6. A [ i +1 ] ← A[ i ]
array A[1],A[2],…….A[i-1] and thus the time can be 7. i ← i -1
2
expressed as a quadratic equation i.e O(n ) But in case of 8. A [i +1] ← key
enhanced insertion technique, it is O(n) as we have just 1
comparisons for the first two elements, rest n-2 have 3.4.5 Stability
just 2 comparisons. For example: As insertion sort is a stable algorithm, enhanced insertion
sort is also stable as a sorting algorithm is stable if
For the average case like this:- whenever there are two records R and S with
the same key and with R appearing before S in the
100 80 70 50 40 20 original list, R will appear before S in the sorted list.
80 100 70 50 40 20 Table showing comparisons:
70 80 100 50 40 20
50 70 80 100 40 20 Table2: Comparison with recently used algorithm
40 50 70 80 100 20
20 40 50 70 80 100
Enhanced Bubble Selection Insertion
Insertion Sort Sort Sort
We get 1+2*4=9comparisons Sort
In general 1+2(n-2) comparisons=O (n)

3.4.3.Example Best Case

Complexit O(n) O(n2) O(n2) O(n)
Consider the same example as below
y
45 30 60 25 70 20 80 75 15 10
Average
30 45 60 25 70 20 80 75 15 10 Case
30 45 60 25 70 20 80 75 15 10 Complexit Less than O(n2) O(n2) O(n2)
25 30 45 60 70 20 80 75 15 10 y
25 30 45 60 70 20 80 75 15 10 O(n1.585)
20 25 30 45 60 70 80 75 15 10
20 25 30 45 60 70 80 75 15 10 Worst Case Less than O(n2) O(n2) O(n2)
20 25 30 45 60 70 75 80 15 10 1.585
O(n )
15 20 25 30 45 60 70 75 80 10
10 15 20 25 30 45 60 70 75 80

38
 International Journal of Computer Applications (0975 – 8887)
Volume 64– No.21, February 2013

Table3:Comparison with various enhanced algorithms complete this task and to my mentor, Mr. Parveen
Kumar for providing support and material related to
Enhanced Enhanced SMS Enhanced the area of this research.
Insertion Selection Algorithm[ Bubble
Sort Sort[3] 8] Sort[3] 6. REFERENCES
[1] Cormen T, Leiserson C, Rivest R and Stein C. 2001.
Introduction to Algorithms, Tata Mc Graw Hill.
Best Case
Complexity O(n) O(n2) O(nlgn) O(nlgn) [2] Surmeet Kaur, Tarundeep Singh Sodhi and Parveen
Kumar, May 2012. Freezing Sort, International
Journal of Applied Information Systems VOL2.
Average [3] Jehad Alnihoud and Rami Mansi, 2010. An
Case Enhancement of Major Sorting Algorithms, The
Complexity Less than O(n2) O(nlgn) O(nlgn)
International Journal of Information Technology
O(n1.585)
VOL7.
[4] Rupesh Srivastava, Tarun Tiwari Sweetesh Singh,
Worst Case Less than O(n2) O(nlgn) O(nlgn)
2009. Bidirectional Expansion–Insertion Algorithm
O(n1.585)
for Sorting. Second International Conference on
Emerging Trend in Engineering and Technology,
ICETET-09.

4. CONCLUSION [5] Muhammad Anjum Qureshi 2010. Qureshi Sort: A

This work focuses to provide an enhancement in new sorting Algorithm.
insertion sort and making enhanced insertion sort [6] Seymour Lipschutz, 2011. Data Structures with C,
more efficient for bigger list as it gives less than Shaum Series.
O(n1.585) complexity in worst case and reduces near
about half comparison. I t does not requires [7] Wang Min, 2010. Analysis on 2-Element Insertion
scanning all elements, because of its hit method it Sort Algorithm, International Conference on
provides a boost to sorting, also reduces the Computer Design And Appliations (ICCDA).
number of comparisons while sorting an array as [8] Rami Mansi,2010. Enhanced Quick Sort Algorithm
2 International Arab Journal of Information
compared to O(n ) complexity of insertion sort, in
fact it is O(n) in best as well as s o m e t i m e s i n Technology.
average case. Furthermore the proposed algorithm is
compared with some recent used algorithms like [9] Basit Shahzad and Muhammad Tanvir Afzal,
bubble sort, selection sort etc. Basically its complexity 2007.Enhanced Shell Sort Algorithm, World
varies from O(n) to O(n1.585) . Academy of Science,Engineering and Technology.
[10] Sultanullah Jadoon, Salman Faiz Solehria,
MubashirQayum. Optimized Selection Sort
5. ACKNOWLEDGEMENT Algorithm is faster than Insertion Sort Algorithm: a
I would like to express my gratitude to all those who Comparative Study, International Journal of Electrical
gave me the possibility to complete this work. I would and Computer Sciences.
like to thank my GOD for giving me strength to

39