Sorting a deque using limited operations?

Question

Hi I came across a question in the Algorithms 4th Edition by Robert Sedgewick.

Dequeue sort. Explain how you would sort a deck of cards, with the restriction that the only allowed operations are to look at the values of the top two cards, to exchange the top two cards, and to move the top card to the bottom of the deck.

I was hoping someone could explain how this would be done, I am really lost. Thanks you

Answer 1

Rather than thinking of the deck having a top and a bottom, imagine that the deck of cards is arranged in a ring. You can imagine having a marker that you place between two specific cards, which then corresponds to the top of the deck. Your operations of "swap the top two cards" is then swapping the two cards to the left of the marker, and the operation of "move the top of the deck to the bottom" then corresponds to moving the marker one step to the left.

Given this, you can naturally adapt bubble sort to work in this setup. Permanently mark one of the positions in the ring as the start point. Then, repeatedly do the following: if the two cards to the left of the marker are out of order, swap them. Then, move the marker one step to the left. As an exception to the rule, if the marker is one step before the marker's initial position, don't do the comparison. If you go around the circle without exchanging anything, you're done!

In pseudocode, this would look as follows:

repeat the following until no swaps are made:
    counting from i = 1 to n - 1, inclusive:
       if the top two cards are out of order, swap them.
       move the top card of the deck to the bottom.
    then, move the top card of the deck to the bottom.

Hope this helps!

Answer 2

A very simple solution is here using java. Just keep shifting the top element by comparing and keep track of the number of sorted elements. On every iteration, it will give us one smallest element based on the position. We will do this based on n and k values. For n values, we will keep shifting based on bigger elements and for k values, we will just keep shifting based on smaller values and eventually, the solution will come. You can try this.

private void sort(Integer[] a) {
        int n = a.length-1,k=1;
        while (n>0){
            for (int i = 0; i < n; i++) {
                if (a[1]>a[0]){
                    int temp = a[0];
                    a[0] = a[1];
                    a[1] = temp;
                }
                pushToBackAndShift(a);
            }
            for (int i = 0; i < k; i++) {
                if (a[1]<a[0]){
                    int temp = a[0];
                    a[0] = a[1];
                    a[1] = temp;
                }
                pushToBackAndShift(a);
            }
            n--;k++;
        }
        pushToBackAndShift(a);
    }

private void pushToBackAndShift(Integer[] a) {
        int temp = a[0];
        for (int i = 0; i < a.length-1; i++) {
            a[i] = a[i+1];
        }
        a[a.length-1] = temp;
    }