The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.3k views
The minimum number of comparisons required to sort $5$ elements is ____
asked in Algorithms by Veteran (59.5k points)
edited by | 1.3k 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.

1 Answer

+25 votes
Best answer

Answer is 7.

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

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

answered by Boss (34.1k points)
edited by
0
See the above link. The technique is given by Knuth :)
+4
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
Didn't understand from the links given in the answer.

Can someone plz explain in simple terms?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,072 questions
44,645 answers
127,047 comments
43,699 users