Как я могу отсортировать 5 положительных чисел?

Question

У меня есть случайная коллекция из 5 уникальных целых чисел от 1 до 15, которые я хочу отсортировать в порядке возрастания справа налево.

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

Правила:

Мы можем «видеть» только три крайних справа целых за один раз (7 3 4) в (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)

двойной обмен , крайнее правое число заменяется вторым элементом, а затем заменяется третьим элементом. Самое правое целое число перемещается на 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

Вот еще одно решение. На этот раз я создал служебную функцию 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)

Answer 2

Я создал работающую 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() функции без их определения, но их реализация тривиальна, особенно они всегда работают с первыми тремя элементами коллекции.