# Driftsort an array

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 , so the shortest program in bytes.

## Test cases

input => output
 => 
[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]

• An easy way to check if a list is driftsortable is if sorted(l) is a contiguous sublist of l+l.
– xnor
Apr 21, 2016 at 18:52
• Just to clarify: If our language supports negative integers, they can occur in the input, yes? Apr 21, 2016 at 20:59
• @Dennis that is correct. Apr 21, 2016 at 21:00
• Shouldn't this be called shiftsort? Apr 24, 2016 at 15:40
• @FilipHaglund I thought about calling it that, but it may cause confusion with the shift operation that removes the first element of an array. Apr 24, 2016 at 15:56

# Ruby, 33

->a{a.any?{a.sort==a.rotate!}&&a}


a.any? fires up to once for each element in the array, except it stops (and returns true) as soon as the array has been mutated into a sorted state. If this happens, we return the mutated array. Otherwise we return the false value that any? returns.

• This is super clever, particularly the in-place rotate. Nice work! Apr 21, 2016 at 18:26
• Alas, my own Ruby answer has been bested. +1 Apr 21, 2016 at 18:53
• Ah yes, the old "sort it until you can tell if it's able to be sorted" technique. Apr 22, 2016 at 15:13

## Python 2, 51 bytes

lambda l:sorted(l)*(map(cmp,l[-1:]+l,l).count(1)<3)


Doesn't bother rotating. Instead, sorts the list, then sees if the original is drift-sortable by checking if there's at most one decrease among consecutive elements of the cyclified list. The count is <3 because map pads the shorter list with None at the end, adding a fake decrease.

• [1, 3, 2, 4] only has one decrease among consecutive elements but it's not drift-sortable.
– Neil
Apr 21, 2016 at 18:23
• @Neil Oh shoot.
– xnor
Apr 21, 2016 at 18:24
• @Neil I think this fixes it. Could you please take a look?
– xnor
Apr 21, 2016 at 18:35
• Aw we <3 you too
– Nic
Apr 21, 2016 at 19:25
• I can't say I'm expert at Python but that seems reasonable assuming the <3 is to avoid having to precisely rotate the list.
– Neil
Apr 21, 2016 at 20:11

## Pyth, 9 bytes

*SQ}SQ.:+


Explanation:

           - Q = eval(input())
+ -    Q+Q
.:  -   sublists(^)
}       -  V in ^
SQ     -   sorted(Q)
*SQ        - ^ * sorted(Q) (return sorted(Q) if ^ True)


Try it here!

Or use a test suite!

• I think you mean substrings (sublists) for .:. Combinations would include non-contiguous elements.
– xnor
Apr 21, 2016 at 19:24

# Jelly, 6 bytes

ṙỤċṢȧṢ


### How it works

ṙỤċṢȧṢ  Main link. Argument: A (list)

Ụ      Grade up; return the indices of A, sorted by their corresponding values.
ṛ       Rotate A by each index, yielding the list of all rotations.
Ṣ    Yield A, sorted.
ċ     Count the number of times sorted(A) appears in the rotations.
This gives 0 if the list isn't driftsortable.
ȧṢ  Logical AND with sorted(A); replaces a positive count with the sorted list.

• Ahem, 19 bytes of UTF8. Apr 21, 2016 at 21:37
• Jelly has a custom code page that encodes each of the 256 characters it understands as single bytes. (It's 16 bytes with UTF-8 btw.) Apr 21, 2016 at 21:39
• @Dennis: you should copy/paste this in all your Jelly submissions to prevent us (ie, ones who didn't knew this before) from making the same comments ? ;) Apr 22, 2016 at 9:56

# Matlab, 6147 41 bytes

Thanks @Suever for -6 bytes!

@(a)sort(a)+0*min(strfind([a,a],sort(a)))


If strfind([a,a],sort(a)) tries to find the sorted input vector as a 'substring' of the unsorted, that was appended to itself. If true, the input is driftsortable and we get a vector of length 2, if not we get a empty vector. min just transforms this to an number / empty vector. Adding the sorted vector to 0 just displays it, adding it to an empty vector throws an error.

• Does the substring check handle [2, 3] not being a sublist of [12, 34]?
– xnor
Apr 21, 2016 at 19:09
• Yes, each integer array can also interpreted as string, where each number is treated as one character, no matter how big the number. Apr 21, 2016 at 19:34
• @flawr My interpretation is that strfind can work directly with numbers, not only with chars (even though that's not documented). If the numbers were being interpreted as chars they would be limited to 65535 (try for example +char(1e5)) Apr 22, 2016 at 0:00
• @LuisMendo You are right, it even works with floating point numbers. Note that numers above 65535 will just be displayed as a space when considered as part of a string. Apr 22, 2016 at 6:24

# Julia, 7166 52 bytes

x->(y=sort(x))∈[circshift(x,i)for i=1:endof(x)]&&y


This is an anonymous function that accepts an array and returns an array or a boolean. To call it, assign it to a variable.

For an input array x, we construct the set of all rotations of x and check whether the sorted version x is an element of that list. If it is, we return x sorted, otherwise we return false.

Saved 19 bytes thanks to Dennis!

# Pip, 15 + 1 = 17 16 bytes

Ugh, the other golfing languages are blowing this out of the water. However, since I've already written it...

L#gI$<gPBPOgYgy  Takes input as space-separated command-line arguments. Requires -p or another array-formatting flag to display the result legibly rather than concatenated. The false case outputs an empty string, which is visible by virtue of the trailing newline.  Implicit: g is array of cmdline args; y is empty string L#g Loop len(g) times: POg Pop the first item from g gPB Push it onto the back of g$<             Fold on < (true if g is now sorted)
I        Yg     If true, yank g into y
y  Autoprint y


## JavaScript (ES6), 7270 65 bytes

a=>a.map(y=>{c+=x>y;x=y},x=a.slice(c=-1))|c<1&&a.sort((a,b)=>a-b)


Returns 0 on failure. Previous 85 83 80-byte version avoided calling sort:

a=>a.map((y,i)=>{x>y&&(c++,j=i);x=y},x=a.slice(c=-1))|c<1&&a.splice(j).concat(a)


Edit: Saved 2 bytes by initialising c to -1 instead of 0. Saved 5 bytes by switching from reduce to map, sigh...

• See the edit ;) Apr 21, 2016 at 18:52
• Call to sort for numbers is incorrect. Check on the sample [10, 2, 3, 4, 7]. Apr 21, 2016 at 20:28
• This code also failes 3 tests: , [0, 0, 0, 0, 0, 0, 0] and [75, 230, 30, 42, 50]. Apr 21, 2016 at 20:43
• @Qwertiy Sorry about the sort oversight, which caused the third test failure. The other two test failures were caused by me over-golfing; I've reverted to the previous version.
– Neil
Apr 21, 2016 at 22:48

# 05AB1E, 12 bytes

Code:

DgFÀÐ{Qi,}}0


Uses CP-1252 encoding. Try it online!.

## Snowman 1.0.2, 27 bytes

((}#AsO|##aC,as|aLNdEaR*))


This is a subroutine that takes input from and outputs to the current permavar.

Try it online!

((                       ))  subroutine
}                          set our active variables b, e, and g:
.[a] *[b] .[c]
.[d]      *[e]    (* represents an active variable)
.[f] *[g] .[h]
#                         store the input in variable b
AsO                      sort in-place
|                     swap b with g; now sorted input is in g
##                   store the input again in b and e
aC                 concat; now the input doubled is in b and e is empty
,                swap e/g; now b has 2*input and e has sorted input
as              split 2*input on sort(input) and store result in g
|             bring the result up to b (we no longer care about g)
aLNdE        take length and decrement; now we have 0 in b if the
array is not driftsortable and 1 if it is
aR     repeat e (the sorted array) b times:
if b is 0 (nondriftsortable), returns [] (falsy)
otherwise (b=1), returns sorted array unchanged
*    put this back into the permavar


# MATL, 131210 9 bytes

SGthyXfa*


The same idea as @flawr's answer where we hijack strfind (Xf) to find the sorted version of the input within the concatenation of two copies of the input.

Try it Online!

Explanation

        % Implicitly get input
S       % Sort the input
Gth     % Explicitly grab the input again and concatenate with itself
y       % Copy the sorted version from the bottom of the stack
Xf      % Look for the sorted version as a subset
a       % Gives a 1 if there were matches and 0 otherwise
*       % Multiply by the sorted array. Yields all zeros for no match and the
% sorted array when a match was found
% Implicitly display the stack contents

• Can't you remove g? Or replace ng by a Apr 21, 2016 at 21:02
• @LuisMendo Can't replace with just an n because n could be > 1. a definitely works though. I figured there was a better way. Thanks! Apr 21, 2016 at 21:03

# Julia, 33 bytes

x->sum(diff([x;x]).<0)<3&&sort(x)


Try it online!

### How it works

This concatenates the array x with itself and counts the number of pairs that are out of order, i.e. the number of contiguous subarrays [a, b] for which b - a < 0. If c is the number of unordered pairs of x itself and t is 1 if x's last element is larger than its first, sum will return 2c + t.

The array x is driftsortable iff (c, t) = (1, 0) (x has to be rotated to the smaller value of the only unordered pair), (c, t) = (0, 1) (x is sorted) or (c, t) = (0, 0) (x is sorted and all of its elements are equal), which is true iff 2c + t < 3.

# Javascript ES6, 4845 43 chars

x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x


Test:

f=x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x
; => 
[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]
.split
.map(t => t.replace(/^(.*) => (.*)$/, "f($1)+'' == $2")).every(eval)  • I think you can save two bytes by using (x+[,x]) and a further byte by using ~ instead of 1+ in your condition. – Neil Apr 21, 2016 at 22:57 • @user6188402, yep, thank you. May 9, 2016 at 20:08 # Brachylog, 39 bytes l:0re:?{[0:L],!L.|rh$(L,?h-1=:L:1&.}.o.


I really need to add an optional argument to $( - circular permute left to permute more than once... this would have been 13 bytes. This will wait after implementing a stable new transpiler in Prolog. ### Explanation l:0re I = a number between 0 and the length of Input :?{[0:L],!L.|rh$(L,?h-1=:L:1&.}      All this mess is simply circular permutating the
input I times
.o.   Unify the Output with that circular permutation
if it is sorted, else try another value of I


# Ruby, 47 bytes

Recursive function. Returns nil if the input array cannot be driftsorted.

f=->a,i=0{a.sort==a ?a:a[i+=1]?f[a.rotate,i]:p}


## CJam, 17 13 bytes

Thanks to Dennis for saving 4 bytes.

{_$\_+1$#)g*}


An unnamed block (function) which takes and returns a list.

Test suite.

### Explanation

This essentially uses xnor's observation that the sorted list appears in twice the original list if its drift sortable:

_$e# Duplicate input and sort. \_+ e# Get other copy and append to itself. 1$   e# Copy sorted list.
#    e# Find first position of sorted list in twice the original,
)g   e# Increment and take signum to map to 0 or 1.
*    e# Repeat sorted array that many times to turn it into an empty
e# array if the input was not drift sortable.

• @Dennis oh, looks like we came up with that independently. Thanks though. :) Apr 21, 2016 at 20:30

# C++ 14, 242 chars

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}}


If I can't leave output empty, 252 chars http://ideone.com/HAzJ5V

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}cout<<'-';}


Ungolfed version http://ideone.com/Dsbs8W

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define b v.begin()

int main()
{
vector <int> v;
int x, n=0;

for(;cin>>x;++n)
v.push_back(x);

for(x=n;x--;rotate(b,b+1,b+n))
if(is_sorted(b,b+n))
{
for(x:v) cout<<x<<' ';
return 0;
}

cout << '-';
}


PS: Based on @MichelfrancisBustillos's idea.

# Java 7, 207 bytes

int[]D(int[]i){int x,z;z=x=-1;int[]d=new int[i.length];while(++x<i.length)if(i[x]>i[(x+1)%i.length])if(z<0)z=(x+1)%i.length;else return null;if(z<0)z=0;x=-1;while(++x<d.length)d[x]=i[z++%i.length];return d;}


Detailed try here

// driftsort in ascending-order
int[] D(int[]i)
{
int x = -1,z = -1;
int[] d = new int[i.length];

while ((++x) < i.length)
{
if (i[x] > i[(x+1)%i.length])
{
if(z < 0) z = (x+1)%i.length;
else return null; // not driftsortable
}
}

if(z < 0) z = 0;
x = -1;
while ((++x) < d.length)
{
d[x] = i[(z++)%i.length];
}

return d;
}


# Java 175

prints out the output as space separated values, or prints f for a falsey value.

void d(int[]a){String s;for(int v,w,x=-1,y,z=a.length;++x<z;){v=a[x];s=""+v;for(y=0;++y<z;v=w){w=a[(x+y)%z];if(v>w){s="f";break;}s+=" "+w;}if(y==z)break;}System.out.print(s);}


goes through all the combinations of the array of integers until it finds the valid sequence or runs out of combinations. the array isn't modified, but instead the driftsorted sequence is stored as a space delimited string.

void driftsort(int[]array){
String str;
for(int previous,current,x=-1,y,len=array.length;++x<len;){
previous=array[x];
s=""+previous;
for(y=0;++y<len;previous=current){
current=array[(y+x)%len];
if(previous>current){
str="false";
break;
}
str+=" "+current;
}
if(y==len)break;
}
System.out.print(str);
}


try it online

# C, 105 bytes

i,s;main(c,v)char**v;{c--;while(i++<c)if(atoi(v[i])>atoi(v[i%c+1]))c*=!s,s=i;while(--i)puts(v[s++%c+1]);}


This accepts the input integers as separate command-line arguments and prints the output list as one integer per line.

If the list isn't driftsortable, the program exits prematurely due to a floating point exception, so its empty output represents an empty list.

### Verification

$gcc -o driftsort driftsort.c 2>&-$ ./driftsort 1 | cat
1
$./driftsort 5 0 5 | cat 0 5 5$ ./driftsort 3 2 1 | cat
$./driftsort 0 9 3 | cat$ ./driftsort 1 2 3 4 | cat
1
2
3
4
$./driftsort 4 1 2 3 | cat 1 2 3 4$ ./driftsort 0 2 0 2 | cat
$./driftsort 5 3 9 2 6 7 | cat$ ./driftsort 0 0 0 0 0 0 0 | cat
0
0
0
0
0
0
0
$./driftsort 75 230 30 42 50 | cat 30 42 50 75 230$ ./driftsort 255 255 200 200 203 | cat
200
200
203
255
255


## Ruby, 28

->a{(a*2*?,)[a.sort!*?,]&&a}


Returns either the sorted array, or nil (which is a falsy value) if the input is not drift-sortable.

# Python, 53 bytes

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))


If you want to test this head over to https://www.repl.it/languages/python3 and copy paste this:

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))
print(N([1,2,3,4,5,0]))


How it works:

• s is a variable storing the sorted python function which sorts lists
• N is the main function
• The input list sorted: s(x) is multiplied by whether or not the list is driftsortable str(s(x))[1:-1]in str(x+x) (thanks to @xnor)
• This works because [1,2,3,4]*false results in an empty list []
• and [1,2,3,4]*true results in [1,2,3,4]
• In Python 2, you can shorten this to lambda x,s=sorted:(s(x)[1:-1]inx+x)*s(x) for 44 bytes. May 10, 2016 at 19:18

# Python, 83 bytes

def f(l):g=sorted(l);return g if any(l[x:]+l[:x]==g for x in range(len(l)))else 1>2


This got put to shame by the other python answers, but I might as well post it anyway. I really dislike the

range(len(l)))


part. Is there a faster way to iterate through the list?

• It's not much, but l.append(l.pop(0))or g==l for _ in l saves a byte over the range-len approach. Using a lambda would save 14 additional bytes. Apr 22, 2016 at 7:06

# MATLAB/Octave, 118 bytes

function r(a)
i=0
while (~issorted(a) && i<length(a))
a=a([2:end 1]),i=i+1
end
if issorted(a)
a
else
0
end

• I think you can already save some bytes by writing everything on one line and using input(''). Also avoid unnecessary spaces and parenthesis! And you can again shed some bytes by first defining f=@issorted. Apr 21, 2016 at 19:41

## PowerShell v2+, 87 80 bytes

param($a)0..($a.length-1)|%{if($a[$_-1]-gt$a[$_]){$c--}};(0,($a|sort))[++$c-ge0]  Steps through the input list $a, checking each pairwise element (including the last and first) to see if there is more than one decreasing pair. If the particular pair is decreasing, we decrement $c. Outputs either the sorted list, or single element 0, based on the value of $c at the end. If more than one "bad" pair is present, then ++$c will still be negative, otherwise it will be at least 0, so the second element of the pseudo-ternary is chosen ($a|sort).

I see xnor did something similar, but I came up with this independently.

# Factor, 47 bytes

[ dup dup append [ natural-sort ] dip subseq? ]


join the sequence onto itself, then check if the sorted rendition of the original is a subsequence.

• This sounds like a philosophical haiku: dup dup append \\ natural sort \\ dip subseq? Even fits the 4-4-3 pattern :)
– user38962
Apr 22, 2016 at 5:30
• @Akiiino :D point-free languages are so poetic.
– cat
Apr 22, 2016 at 8:04

## C++, 313 359370 bytes

Huge shoutout to @Qwertiy for getting this working and teaching me some great golfing methods!

### Golfed:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> v;int x,c=0,s=0,y;while(cin>>x)v.push_back(x);do if(rotate(v.begin(),v.begin()+1,v.end()),c++,is_sorted(v.begin(),v.end()))s=1;while(!s&c<=v.size());if(s)for(y=0;y<v.size();y++)cout<<v[y]<<" ";else cout<<"False";}


### Ungolfed:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
vector <int> v;
int x, c=0, s=0, y;

while(cin>>x)
v.push_back(x);

do
if (
rotate(v.begin(),v.begin()+1,v.end()),
c++,
is_sorted(v.begin(),v.end())
) s = 1;
while(!s & c <= v.size());

if (s)
for(y=0; y<v.size(); y++)
cout<<v[y]<<" ";
else
cout<<"False";
}

• Golfing isn't just removing spaces. using namespace std; is 20 chars when std:: 6 times is 30. bool s = False; - why not =0? You can drop return 0;. Why are brackets here !s&&(c<=v.size())? Figure braces and no commas... Apr 21, 2016 at 21:05
• Wow, thanks! A Lot of stuff (like std:: and return 0;) has become habit from programming classes. I really need to start checking my programs better. Apr 21, 2016 at 21:10
• Also there is a set of bugs. Why do you read until zero and put that zero into data? Why do you output to size inclusive? Why True and False instead of true and false. ideone.com/kVTI25 - your version, ideone.com/y8s44A - fixed and prepared for golfing version. Apr 21, 2016 at 21:26
• Thank you again! Caping True and False is from Python. I didn't even know you could write ifs like that! Apr 21, 2016 at 21:34
• And much more shortened: ideone.com/Dsbs8W and golfed ideone.com/HAzJ5V (<s>255</s> 252 chars). Used C++14 for foreach loop. Apr 21, 2016 at 21:45 In Mathcad, 0 (scalar) == false.

(Equivalent) byte count is TBD until counting method agreed. Approx 52 bytes using a byte = operator / symbol keyboard equivalence.

# Mathematica 55 50 61 58 bytes

With 3 bytes saved thanks to Martin Büttner.

My earlier attempts did not pass all of the test case. I needed to add Union to avoid repetitions in list that were input in order.

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&


Tests

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&/@
{{1},{5,0,5},{3,2,1},{0,9,3},{1,2,3,4},{4,1,2,3},{0,2,0,2},{5,3,9,2,6,7},
{0,0,0,0,0,0,0},{75,230,30,42,50},{255,255,200,200,203}}


{{1}, {0, 5, 5}, {}, {}, {1, 2, 3, 4}, {1, 2, 3, 4}, {}, {}, {0, 0, 0, 0, 0, 0, 0}, {30, 42, 50, 75, 230}, {200, 200, 203, 255, 255}}

Explanation

Right rotate the input list from 1 to n times, where n is the length of the input list. If the sorted input list is among the output rotated lists, return it; otherwise return an empty list.

• @MartinBüttner, Your suggestion failed in some of the test cases, specifically, #s 3,4,7,8. Apr 22, 2016 at 15:33
• @DavidC Ah, damn, you're right, I mixed up the behaviour of @@ and /@ on empty lists. Join@@ should still be shorter than Flatten@ though. Apr 22, 2016 at 16:35

# PHP, 98 bytes

Outputs a 1 if driftsortable, else nothing

$a=$argv;$b=$a;sort($a);foreach($a as $v){echo($a===$b?1:'');array_unshift($b, array_pop(\$b));}