使用有限的操作对双端队列进行排序？ [英] Sorting a deque using limited operations?

问题描述

我在Robert Sedgewick的Algorithms 4th Edition中遇到了一个问题。

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

推荐答案

而不是想象纸牌有顶部和底部，而是假设纸牌排列在一个环。您可以想象在两个特定的卡之间放置一个标记，该标记然后对应于牌组的顶部。然后，交换前两张卡的操作将两张卡交换到标记的左侧，而将卡座的顶部移动到底部的操作对应于将标记向左移动一个步骤。

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.

希望这会有所帮助！

这篇关于使用有限的操作对双端队列进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！