in Programming
528 views
0 votes
0 votes
Is it always the case that in an unsorted array using comparison based sorting algorithm the minimum number of comparison required to convert it into sorted array is Equal to number of Inversions present in the Array. Am i saying the statement right ?
in Programming
by
528 views

4 Comments

No,

Suppose the array is already sorted in ascending order then the no. of comparisons made is O(n) which is the best case of bubble sort but the number of inversions is 0 (zero) in that case.

May be the number of swaps needed in bubble sort = no. of inversions present in the array.
0
0
Ok thanku sir
0
0

Can the number of inversions ever be O(n logn) ? 

0
0

Please log in or register to answer this question.