如何对 5 个正整数进行排序？

Question

我随机收集了 5 个从 1 到 15 的唯一整数，我想按从右到左的升序对它们进行排序。

Example input:  15 6 7 3 4
Desired output: 15 7 6 4 3

规则：

我们一次只能"see" (7 3 4) in (15 6 7 3 4) 中最右边的三个整数，并且只能对数组 (4) 中最右边的整数。我们还可以在代码中使用最多 5 个整型变量。

可能的操作：

putend,最右边的整数放在数组最左边的位置

(15 6 7 3 4) -> (4 15 6 7 3)

swap，最右边的整数和第二个整数交换。 最右边的整数在数组中向左移动一位。

(15 6 7 3 4) -> ( 15 6 7 4 3)

double swap，最右边的整数先和第二个元素交换再和第三个元素交换。 最右边的整数在数组中向左移动 2 步。

(15 6 7 3 4) -> (15 6 4 7 3).

我的尝试：

while (not solved)
  if first element < 2nd element
    putend
  else if first element > 2nd element
    if first element > 3rd element
        double swap
    else
      swap

输出：

15 6 7 3 4  swap
15 6 7 4 3  putend
3 15 6 7 4  putend
4 3 15 6 7  swap
4 3 15 7 6  putend
6 4 3 15 7  putend
7 6 4 3 15 (problem here, triggers double swap but want putend and somehow detect that I am done)

Answer 1

我创建了一个工作 Python 程序来演示算法，但我认为它对每个人来说都像伪代码一样可读（我使代码非常简单）。解决方案非常残酷，但似乎有效。还有很多进一步优化的潜力。我把描述放在评论中：

x = [15, 12, 3, 2, 13]

def putend():
    x.append(x.pop(0))

def swap():
    x[0], x[1] = x[1], x[0]

def doubleswap():
    x[0], x[1], x[2] = x[1], x[2], x[0]


def put_smallest_back():
  smallest = min(x[0], x[1], x[2])
  if x[2] == smallest:
    # Move smallest to x[1]
    doubleswap()
  if x[1] == smallest:
    # Move smallest to x[0]
    swap()
  putend()

# Put back two smallest values of four to make sure two largest are in front
put_smallest_back()
put_smallest_back()

# Now two largest values are in three accessible cells
# Find and put back second largest
largest = max(x[0], x[1], x[2])
smallest = min(x[0], x[1], x[2])
if x[2] != largest and x[2] != smallest:
  doubleswap()
if x[1] != largest and x[1] != smallest:
  swap()
putend()

# Find and put back largest
# Largest is in x[0] or x[1]
if x[1] == largest:
  swap()

# Largest is in x[0]
putend()

# Two largest values are sorted
# Time to sort x[2]
if x[0] > x[1] and x[0] > x[2]:
  doubleswap()
elif x[1] > x[0] and x[1] > x[2]:
  swap()
  doubleswap()

# Last step, sort x[0] and x[1]
if x[0] > x[1]:
  swap()

# Voilla!
print(x)

我使用了 min() 和 max() 函数但没有定义它们，但是它们的实现很简单，尤其是它们总是对集合的前三个元素进行操作。

Answer 2

这是另一种解决方案。这次我创建了一个 sort3() 实用函数来对前三项进行排序。这种大大简化的算法现在不需要 min()、max() 或任何其他变量。解决方案是功能齐全的 Python 代码，但与伪代码一样易于阅读：

x = [5, 1, 13, 2, 10]

def putend():
    x.append(x.pop(0))

def swap():
    x[0], x[1] = x[1], x[0]

def doubleswap():
    x[0], x[1], x[2] = x[1], x[2], x[0]

# Sort first 3 elements ascending
def sort3():
    if x[1] > x[0]:  # Ensure larger of first two is x[0]
        swap()
    if x[0] > x[2]:  # If x[0] is largest, doublewsap it to x[2]
        doubleswap()
    if x[0] > x[1]:  # Largest value is in x[2], sort x[0] and x[1]
        swap()

# Put back smallest of first three items
sort3()
putend()

# Put back smallest of first three items again (x[2] is new item)
sort3()
putend()

# Now two largest values are in first three cells
# Find and put back second largest value
sort3()
swap()
putend()

# Put largest back
swap()
putend()

# Two largest values are sorted
# Time to sort the rest
sort3()

# Voila!
print(x)

如何对 5 个正整数进行排序？

How can I sort 5 positive integers?

computer-science

pseudocode