Swapping ints 2
We know that the insertion sort algorithm has a worst-case running time of
in general case. What if we could bound the algorithm for specific instance of the problem. One way to do that is by checking the number of
swap
operations needed by insertion algorithm to sort a list.
In the permutation of of distinct elements the list inversion are pair of elements such that and . What is the worst-case running time if the inputs are restricted to permutations of with at most inversions?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
In a permutation a1...an, of n distinct integers, an inversion is a pair (ai,aj) such that i<j and ai>aj.
One important thing to see is Difference between swap and Inversions. Swapping is done explicitly by the programmer, hence a explicit feature whereas, Inversion is an implicit feature which is defined in the input . Ex :- Take the input => {0,1,9,8,10,7,6,11} How many Inversions here : {9,8} , {9,7} , {9,6} ,{8,7} , {8,6} , {10,7} and {10,6}. Hence, it is an implicit feature of the input and not any explicit operation done (Swap) .
Actual Time complexity of Insertion Sort is defined as Θ(N+f(N)), where f(N) is the total number of Inversions .
Ex :- Again take the input => {0,6,7,8,9,10,1} Here, how many comparisons will be there to place 1 in the right place ?
First of all, 1 is compared with 10 - Returns True as it is smaller than 10. Then, with 9 - again True. Similar, happens with 6,7,8 - All return True . Hence, There 5 comparisons were the Inversions and 1 more comparison will be there, in which outer while loop fails .
For, placing 1 in the right place 6 comparisons are there .
Hence, Total Comparisons in the Insertion sort will be :- Total number of elements for which our while loop fails + Total number of inversions in the input
Total number of elements for which our while loop fails :- Suppose the input {0,6,7,8,9,10,1}. Here, first 0 will be kept as it is and one while loop fail comparison for each element, hence total comparisons like this :- (N−1)=O(N) comparisons. Total number of inversions in the input :- Best Case : 0 and in the Worst Case : N(N−1)2=O(N2) Total Time complexity of insertion sort : Θ(N+f(N))
It is given here that at most N inversions are there, so we get the best Time complexity :- Θ(N+f(N))=Θ(N+N)=Θ(N) .