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

Some Important points from wiki -->

  • 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.


answered by Boss (34.1k points)
edited by
See the above link. The technique is given by Knuth :)
But of array is sorted and i use insertion sort it will take 4 comparisions?
Yes if we use insertion sort on already sorted array of n it takes n-1 comparisons.
even bubble sort on already sorted array will give 4 comparisons right ?
@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?
I am also getting 4 as answer as minimum comparison is being asked.
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
43,699 users