Increasing Time Efficiency of Insertion Sort for the Worst Case Scenario
Don't use plagiarized sources. Get Your Custom Essay on
Increasing Time Efficiency of Insertion Sort
Just from $13/Page
Surabhi Patel, Moirangthem Dennis Singh
Abstract. Insertion sort gives us a time complexity of O(n) for the best case. In the worst case where the input is in the descending order fashion, the time complexity is O(n2). In the case of arrays, shifting is taking O(n2) while in the case of linked lists, comparison is coming to O(n2). Here a new way of sorting for the worst case problem is proposed. We will use arrays as data structures and take more space. We will take 2n spaces where n is the number of elements and start the insertion from (n-1)th location of the array. In this proposed technique the time complexity is O(nlogn) as compared to O(n2) in the worst case.
Keywords. Insertion Sort, Time Complexity, Space Complexity
Introduction
Insertion sort is a simple sorting algorithm[1], a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.
The best case input is an array that is already sorted. In this case insertion sort has a linear running time which is O(n). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
The worst case input is an array sorted in reverse order. In this case, every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time which is O(n2).
The average case also has a quadratic running time of O(n2).
Literature Survey
In an insertion sort algorithm, there are always two constraints in time complexity. One is shifting the elements and the other one is comparison of the elements. The time complexity is also dependent on the data structure which is used while sorting. If we use array as data structure then shifting takes O(n2) in the worst case. While using link list data structure, searching takes more time, viz. O(n2).
We will take the following examples:
Sort 50, 40, 30, 20, 10 using arrays.
Shifting = 0, Comparison = 0
0
1
2
3
4
50
40
40
50
Shifting = 1, Comparison = log1
0
1
2
3
4
40
50
30
40
30
50
30
40
50
Shifting = 2, Comparison = log2
0
1
2
3
4
30
40
50
20
30
40
20
50
30
20
40
50
20
30
40
50
Shifting = 3, Comparison = log3
0
1
2
3
4
20
30
40
50
10
20
30
40
10
50
20
30
10
40
50
20
10
40
40
50
10
20
30
40
50
Shifting = 4, Comparison = log4
Time Complexity in Shifting: O(n2)
Time Complexity in Comparison: O(nlogn)
Total time complexity: O(n2)
Here as the array is sorted, we can use binary search for comparison which will lead to a time complexity of O(nlogn) but Shifting takes O(n2). Therefore the total time complexity becomes O(n2)
To solve this problem, link list can be used as illustrated in the following example.
Sort 50, 40, 30, 20, 10 using link list. In a link list shifting takes O(1) as new elements can be inserted at their right positions without shifting.
Comparison = 0
50
–>
40
40
–>
50
Comparison = 1
40
–>
50
–>
30
30
–>
40
–>
50
Comparison = 2
30
–>
40
–>
50
–>
20
20
–>
30
–>
40
–>
50
Comparison = 3
20
–>
30
–>
40
–>
50
–>
10
10
–>
20
–>
30
–>
40
–>
50
Comparison = 4
Time Complexity in Shifting: O(1)
Time Complexity in Comparison: O(n2)
Total time Complexity: O(n2)
Here as we cannot use binary search for comparison which will lead to a time complexity O(n2) even though shifting takes a constant amount of time.
As we have observed in the examples illustrated above, in both the cases the Time complexity is not getting reduced. Hence we are proposing an improvised insertion sort taking additional space to sort the elements. As space complexity is less important than time complexity[2][3], we have concentrated more over the time taken instead of space.
Proposed Work
In the insertion sort technique proposed here, we will take 2n spaces in an array data structure, where n is the total number of elements. The insertion of elements will start from n-1th position of the array. The same procedure of a standard insertion sort is followed in this technique. Finding the suitable positions of the elements to be inserted will be done using binary search. In the following cases we will discuss the details of our work.
Case 1
For the best case scenario in a standard Insertion Sort is the input elements in ascending order using proposed technique.
e.g. 10, 20, 30, 40, 50
0
1
2
3
4
5
6
7
8
9
10
Shifting =0 , Comparison = 0
0
1
2
3
4
5
6
7
8
9
10
20
Shifting =0 , Comparison = 1
0
1
2
3
4
5
6
7
8
9
10
20
30
Shifting =0 , Comparison = 1
0
1
2
3
4
5
6
7
8
9
10
20
30
40
Shifting =0 , Comparison = 1
0
1
2
3
4
5
6
7
8
9
10
20
30
40
50
Shifting =0 , Comparison = 1
Total Shifting =0, Total Comparison = n-1
Therefore time complexity is O(1)+O(n) = O(n)
Case 2:
For the worst case scenario in a standard Insertion Sort is the input elements in descending order using proposed technique.
e.g. 50, 40, 30, 20, 10
0
1
2
3
4
5
6
7
8
9
50
Shifting =0 , Comparison = 0
0
1
2
3
4
5
6
7
8
9
50
40
40
50
Shifting =1 , Comparison = log1
0
1
2
3
4
5
6
7
8
9
40
50
30
30
40
50
Shifting =1 , Comparison = log2
0
1
2
3
4
5
6
7
8
9
30
40
50
20
20
30
40
50
Shifting =1 , Comparison = log3
0
1
2
3
4
5
6
7
8
9
20
30
40
50
10
10
20
30
40
50
Shifting =1 , Comparison = log4
Total Shifting =n-1,
Total Comparison =log( 1*2*3*4)
=log((n-1)!)
=log((n-1) (n-1))
=(n-1)log(n-1)
=nlog(n-1) – log(n-1)
Therefore time complexity is O(n)+O(nlogn) = O(nlogn)
Case 3:
For the average case scenario in a standard Insertion Sort, the input elements are in random order. We are following the same procedure but comparison is done via binary search algorithm. Hence it takes O(nlogn) for comparison. For shifting the elements, the time taken tends to O(n2) but is not equal to O(n2). As we have more spaces, there are possibilities that the shifting of some elements may be reduced because elements may be inserted both at the end as well as in the beginning.
Results
Now we compare the time complexities of proposed sorting technique and the standard Insertion sort.
Input Elements
Standard Insertion Sort
Proposed Sorting Technique
Best Case (Ascending Order)
O(n)
O(n)
Worst Case (Descending Order)
O(n2)
O(nlogn)
Average Case (Random Order)
O(n2)
Tends to O(n2)
Conclusion
We are decreasing the time complexity of worst case scenario in Insertion sort algorithm by increasing the space complexity. Our future scope of work includes decreasing time complexity of the average case which is O(n2) currently. There are promising results shown in the average case scenario where the time complexity may be reduce from O(n2), if the probability of the input elements is a combination of increasing and decreasing order.
Acknowledgement
We would like to thank Prof Anirban Roy, Department of Basic Sciences Christ University Faculty of Engineering for helpful discussions and support.
REFERENCES
Insertion Sort,http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Insertion_sort.html
Michael A. Bender, “Insertion Sort is O(nlogn),” Third International Conference on Fun With Algorithms(FUN), Pages 16-23, 2004
H. W. Thimbleby, “Using Sentinels in Insert Sort,” Software Practice and Experience, Volume 19(3), Pages 303–307, 1989.
