25
3
Driftsort is a simple way to "sort" an array. It works by "sliding" or "rotating" the elements over in the array until the array is sorted, or until the array fails to be sorted.
Let's walk through two examples. First, consider the array [10, 2, 3, 4, 7]
. Since the array is not sorted, we rotate it once. (This can happen in either direction, so long as it remains the same direction.) Then, the array becomes:
[7, 10, 2, 3, 4]
This is not sorted, so we rotate again.
[4, 7, 10, 2, 3]
And again:
[3, 4, 7, 10, 2]
And a final time:
[2, 3, 4, 7, 10]
And it's sorted! So the array [10, 2, 3, 4, 7]
is driftsortable. Here are all the rotations of the array, for clarity:
[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]
Consider now the array [5, 3, 9, 2, 6, 7]
. Look at its rotations:
[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]
None of these arrays are sorted, so the array [5, 3, 9, 2, 6, 7]
is not driftsortable.
Objective Given a nonempty array/list of integers as input to a program/function, implement driftsort on the input and output it, or output a falsey value (or an empty array/list) if it cannot be driftsorted. The integers are bound to your languages max/min, but this must be at least 255 for the max, and 0 for the min.
You may use built-in sorting methods, but not a built-in which solves the challenge.
This is a code-golf, so the shortest program in bytes.
Test cases
input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]
5An easy way to check if a list is driftsortable is if
sorted(l)
is a contiguous sublist ofl+l
. – xnor – 2016-04-21T18:52:02.593Just to clarify: If our language supports negative integers, they can occur in the input, yes? – Dennis – 2016-04-21T20:59:44.160
@Dennis that is correct. – Conor O'Brien – 2016-04-21T21:00:21.090
Shouldn't this be called
shiftsort
? – Filip Haglund – 2016-04-24T15:40:14.773@FilipHaglund I thought about calling it that, but it may cause confusion with the
shift
operation that removes the first element of an array. – Conor O'Brien – 2016-04-24T15:56:28.360