CMI2011-B-06a

Question

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.

Comments

Tower of Hanoi problem:
TOH(n, L, M, R)  // n is number of discs, L=Source, R=Destination
{
if(n==0)
return
else
{
TOH(n-1,L,R,M);
Move(L,R);
TOH(n-1,M,L,R);
}
}

$T(n) = 2T(n-1)+C$

T.C=$O(2^n)$

Using Dynamic Programming:

$T.C = O(n),$ $S.C=O(n)$

---

is it really need TOH problem? I donot think so.

Because, in TOH, we can never put a smaller disk below a wide disk (while swapping).

But here we got no such restriction

right?

Answer 1

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.

Comments

wat a nice explanation @ahwan

---

overall its O(n²) where n is number of disks. Right?

---

very easy to understand explanation thanks ahwan

---

Pancake sorting: Youtube, Wiki

---

what will be the complexity of this algo O($n^2$) or O($2^n$)? @Ahwan

---

Rotating twice takes O(n)..

For 'n' elements ... the T.C. is O(n^2) only.

---

@ Ahwan    mehul vaidya

n+(n-1)+(n-2)+….+1…………….for searching  largest ,second largest element …...so on

similarly O(n square) for rotation ….(n-1,n respective rotation for lagest element then n-2,n-1 for second lagest ………..so (n-1+n)+(n-2+n-1)+…………..+(1)….

hence O(n sq) 

is this the procedure to compute complexity.

Answer 2

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$.

Comments

wat a nice explanation @krish

Answer 3

//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 
        
    }
}