CODEWITHSUNDEEP
arraysalgorithmsorting
Rodrigo
Rodrigo

Reputation: 177

Sorting 4 numbers with minimum x<y comparisons

This is an interview question. Say you have an array of four ints named A, and also this function:

int check(int x, int y){
   if (x<=y) return 1;
   return 0;
}

Now, you want to create a function that will sort A, and you can use only the function checkfor comparisons. How many calls for check do you need?
(It is ok to return a new array for result).

I found that I can do this in 5 calls. Is it possible to do it with less calls (on worst case)?

This is how I thought of doing it (pseudo code): 

int[4] B=new int[4];
/* 
The idea: put minimum values in even cells and maximum values in odd cells using check. 
Then swap (if needed) between minimum values and also between maximum values.
And finally, swap the second element (max of minimums) 
and the third element (min of maximums) if needed.
*/
if (check(A[0],A[1])==1){ //A[0]<=A[1]
    B[0]=A[0];
    B[2]=A[1];
}
else{
    B[0]=A[1];
    B[2]=A[0];  
}
if (check(A[2],A[3])==1){ //A[2]<=A[3]
    B[1]=A[2];
    B[3]=A[3];
}
else{
    B[1]=A[3];
    B[3]=A[2]; 
}
if (check(B[0],B[1])==0){ //B[0]>B[1]
    swap(B[0],B[1]);
}
if (check(B[2],B[3])==0){ //B[2]>B[3]
    swap(B[2],B[3]);
}
if (check(B[1],B[2])==0){ // B[1]>B[2]
    swap(B[1],B[2]);
}

Upvotes: 1

Views: 1451

Answers (2)

Richard
Richard

Reputation: 61309

In The Art of Computer Programming, p. 183 (Section 3.5.1), Donald Knuth has the following table of lower and upper bounds on the minimum numbers of comparisons:

Donald Knuth, TAOCP, p. 183, Section 3.5.1

The ceil(ln n!) is the "information theoretic" lower bound, whereas B(n) is the maximum number of comparisons in an insertion binary sort. Since the lower and upper bounds are equal for n=4, 5 comparisons are needed.

The information theoretic bound is derived by recognizing that there are n! possible orderings of n unique items. We distinguish these cases by asking S yes-no questions in the form of is X<Y?. These questions form a tree which has at most 2^S tips. We need n!<=2^S; solving for S gives ceil(lg(n!)).

Incidentally, you can use Stirling's approximation to show that this implies that sorting requires O(n log n) time.

The rest of the section goes on to describe a number of approaches to creating these bounds and studying this question, though work is on-going (see, for instance Peczarski (2011)).

Upvotes: 2

recursive
recursive

Reputation: 86094

There are 24 possible orderings of a 4-element list. (4 factorial) If you do only 4 comparisons, then you can get only 4 bits of information, which is enough to distinguish between 16 different cases, which isn't enough to cover all the possible output cases. Therefore, 5 comparisons is the optimal worst case.

Upvotes: 5

Related Questions