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

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.

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

answered by Boss (34k points)
edited by
0
See the above link. The technique is given by Knuth :)
+6
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?
0
Not clear about the given answer. I think it should be 4.
0
I didn't got the explanation can someone help?
0
0
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).

Answer-7

 

answered by Boss (14.1k points)
0
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.
0
Yes, in this case it's 4 :O
I need to relook now.
0
as they havenot mentioned any criteria so i am confused :/
0
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
147,406 comments
62,387 users