1.2k views
The minimum number of comparisons required to sort $5$ elements is ____
edited | 1.2k views
+2

Some Important points from wiki -->

https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

• If the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2f(n) cases because the keys are distinct and each comparison has only two possible outcomes.
• Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known.

Minimum number of comparisons = $\lceil \log(n!) \rceil$ =  $\lceil \log(5!) \rceil$ = $\lceil \log(120) \rceil$ = 7.

Ref: http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

edited by
+6
0
See the above link. The technique is given by Knuth :)
+3
But of array is sorted and i use insertion sort it will take 4 comparisions?
0
Yes if we use insertion sort on already sorted array of n it takes n-1 comparisons.
0
Yes.
+1
even bubble sort on already sorted array will give 4 comparisons right ?
0
@Arjun sir, here we are answering for the worst case, right? Otherwise, if array is sorted and I use insertion sort it will take 4 comparisions, right?
0
I am also getting 4 as answer as minimum comparison is being asked.
0

Can someone plz explain in simple terms?