edited by
1,743 views
12 votes
12 votes
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is at the bottom of the pile. The only operation available for manipulating the disks is to pick up a stack of them from the top of the pile and invert that stack. (This corresponds to lifting up a stack $\text{dosas}$ or $\text{chapatis}$ between two big spoons and flipping the stack.)

Give an algorithm for sorting the disks using this operation.
edited by

3 Answers

Best answer
27 votes
27 votes

Let's say we have disk of radius $0$,$5$,$1$,$4$,$3$,$2$

We have many disks, one above other, our task is to arrange them from largest disk to smaller disk.
The only operations available is, take a couple of disks from the top, hold it in your hand, rotate it & put it back.
Just imagine in a real scenario.
How we will do it.

$0$,$5$,$1$,$4$,$3$,$2$

What I will do is, I will take all plates from $5$ to $2$  $(5,1,4,3,2)$ I hold them in my hand, rotated my hand $180$ degree & put it back.
$0,2,3,4,1,5$
Now I will rotate all.
$5,1,4,3,2,0$
Now $5$ is at its right place. We will not consider it.

Now find the second largest plate... $4$.. rotate from $4$ to $0$
$5 \ | \ ,1,0,2,3,4$
rotate from $1$ to $4$.

$5,4 \ |,3,2,0,1$
Now $4$ is at its right place.

Next maximum is $3$, it is at its right place, so we may add one more line in the code to reduce steps...
Otherwise, the same algo will also keep $3$ at it's right place.
The same algo will sort them at last.

Hence, our algo is:
Step 1:
Find the current largest element.
Step 2:
Rotate the elements from largest element to end of the array. (Hold the disks from disk of max size to disk at top & rotate)
Step 3:
Now rotate the array from current start$+1$ to top.

Continue this process till it is sorted.
Note that initially current_start $= -1$  it will be incremented by one every time we get our largest disk placed at its correct place.

edited by
2 votes
2 votes

Assuming a stack of size $N$, find the largest element ($k^{th}$ position) and rotate the stack through it. Now, we have an intermediate state where the largest element is the top. Rotate the complete stack to get the final state. Now, repeat the above steps taking $N = N-1$ till we get a stack of size $1$.

0 votes
0 votes
//psuedo code
//assume that 1st index is 1
Sort( disks, size ){
    
    for (i = 1 to size){ //after each iteration ith place stores correct disk
        
        // FindMax(i,j) returns index of largest disk in range i to j
        max_pos = FindMax( i, size );
        
        if( max_pos != size ){
            Invert( max_pos, size ) //inverts stack from max_pos to size
        }

        //Now we have next maximum disk at top of stack, so invert the stack accordingly
        Invert( i, size ) //Inverts entire stack from ith position 
        
    }
}

 

Related questions