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

2 Answers

+26 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 (34k 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?
Not clear about the given answer. I think it should be 4.
I didn't got the explanation can someone help?
I think, lower bound is asked, it will be log(n!) only.

lower order is generally given for a problem not for an algorithm.

Lower bound of a problem means best algo that can solve the problem(in every case).
0 votes

It is asked minimum number of comparisons to sort 5 elements

Insertion sort performs the minimum number of comparisons to sort 5 elements

Assuming my array is almost sorted (but not completely sorted)

A[0] A[1] A[2] A[3] A[4]
2 3 4 5 1

Now my insertion sort runs from 1 to 4 indices of the array as elements A[0..j-1] are assumed to be sorted and at the start of the algorithm, j=1 so A[0,,,0] contains only one element, so it is sorted.

Now I compare 3 with 2 and check if 3 is less? (No)--1 Comparison

Array A[0,1] sorted.

Now again A[2] compared with A[1].3<4. No Swap required. 1 Comparison.

Similarly one comparison for A[3].

Now When I need to put A[4] into the correct place, How many comparisons do I need to make before 1 is placed in correct position?

1 Comparison with 5 and 1 swap so now array becomes

A[0] A[1] A[2] A[3] A[4]
2 3 4 1 5

Now again 1 comparison among A[2] and A[3] and they are swapped(1 Swap).

A[0] A[1] A[2] A[3] A[4]
2 3 1 4 5

And so sort array 2 more comparisons and 2 more swaps and array finally is

A[0] A[1] A[2] A[3] A[4]
1 2 3 4 5


So, total comparisons=7, total swaps=4.

So, minimum comparisons to sort the array is 7 assuming the array is almost sorted but not completely sorted.

So I think question asks this only, assuming array to be not completely sorted, but almost sorted(means some elements are in correct order).



answered by Boss (14.1k points)
cant it be 4. if we apply insertion sort to almost sorted array. like 2,1,3,4,5 and we apply insertion sort.


as they havent mentioned abt any sorting procedure of arrangement of element.
Yes, in this case it's 4 :O
I need to relook now.
as they havenot mentioned any criteria so i am confused :/
Give me some time and I'll look into it

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

41,069 questions
47,668 answers
62,387 users