1,290 views
0 votes
0 votes
Which sorting algorithim is best if

exhactly only half of the elements are in correct position ?

2 Answers

Best answer
2 votes
2 votes
In insertion sor, the term $O(n^2)$ comes in the worst case, when the list is sorted in reverse order and then every element has to be move to its correct position.

The least element will be compared with every other n-1 elements, the next one with n-2 and so on, so total number of movement will be:

$T(n) = (n-1)+(n-2)+....1$

which is:

$T(n) = \frac{(n-1)n}{2} = O(n^2)$

Now just saying that if half of the elements are sorted then Insertion Sort will work best will not work as it depends on where those "sorted elements" are present. For eg, if the list is  like this:

1,2,3,4,5,9,10,7,8,6 where the first 5 at correct position and the rest 5 are not then the Insertion Sort will work only on the later part of the list.

Here the total number of comparison will be:

$T(n) = \frac{(\frac{n}{2}-1)\frac{n}{2}}{2}  $ and whether it performs better than $O(nlogn)$ will depend on the value of n.

However if the list is something like this:

1,10,3,8,5,6,7,4,9,2, where 5 of the elements are correct position and the rest of the 5 are not then the insertion sort, during its working will disturb the position of those corrects one.
selected by
0 votes
0 votes

Insertion sort is best algorithm for nearly sorted data.

edited by

Related questions

0 votes
0 votes
2 answers
2
_Madhuri asked Oct 9, 2021
631 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
1 votes
1 votes
1 answer
4
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...