Sorting a deck of cards

How can we sort a deck of cards knowing that we can only look at the top cards, exchange the top cards, and moving the top card to the bottom of the stack?

We can start with searching for the lowest card in the deck, for at most n-1 operations. We draw the top two cards and we move the higher one to the bottom. Once we found the lowest card, we move it to the bottom.

We start searching for the second lowest card in the deck, for at most n-2 operations; we don’t have to consider the lowest card, which sits at the bottom. We draw the top two cards and we move the higher one to the bottom. We found the second lowest card in the stack and it sits in the top of the stack. Next card that we draw is the smallest card and we place it at the bottom, followed by the second smallest.

We repeat these steps.

The code below is the Java implementation of the algorithm above.

public static void sort(final Deque<Item> deque) {
    int sorted = 0;
    while (sorted != deque.size()) {
        for (int i = 0; i < deque.size() - sorted - 1; i++) {
            final Item item1 = deque.popLeft();
            final Item item2 = deque.popLeft();
            if (item1.compareTo(item2) >= 0) {
                deque.pushRight(item1);
                deque.pushLeft(item2);
            } else {
                deque.pushRight(item2);
                deque.pushLeft(item1);
            }
        }
        final Item item = deque.popLeft();
        for (int i = 0; i < sorted; i++)
            deque.pushRight(deque.popLeft());
        deque.pushRight(item);
        sorted++;
    }
}
Advertisements