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

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

+23 votes
Best answer

Answer: 7

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

answered by Veteran (35.9k 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.
Yes.
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.


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

32,693 questions
39,293 answers
110,109 comments
36,701 users