How can I sort 5 positive integers?

Question

I have a random collection of 5 unique integers ranging from 1 to 15 that I want to sort in ascending order from right to left.

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

Rules:

We can only "see" the three rightmost integers at a time (7 3 4) in (15 6 7 3 4) and can only take actions on the rightmost integer in the array (4). We can also use up to 5 integer variables in the code.

Possible actions:

putend, the rightmost integer is placed at the leftmost position of the array

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

swap, the rightmost integer is swapped with the second integer. Rightmost integer is moved one step left in the array.

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

double swap, the rightmost integer is swapped with second element and then swapped with the third element. Rightmost integer is moved 2 steps left in the array.

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

My attempt:

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

Output:

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)

user_29564 · Answer

I created a working Python program to demonstrate algorithm, but I think it's as readable as pseudocode for everyone (I made code dead simple). Solution is quite brutal, but seems to be working. There's also lot of potential for further optimizations. I put descriptions in comment:

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)

I used min() and max() functions without defining them, but their implementation is trivial, especially they always operate on first three elements of collection.

user_29564 · Answer

Here's one more solution. This time I created a sort3() utility function that sorts first three items. This greatly simplified algorithm and now doesn't require min(), max() nor any additional variables. Solution is fully functional Python code, but as easy to read as pseudocode:

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)

How can I sort 5 positive integers?

2 Answers