Sever-sort an array

Question

Challenge

Given a non-empty array of integers, e.g.:

[5, 2, 7, 6, 4, 1, 3]

First sever it into arrays where no item is larger than the previous (i.e. non-ascending arrays):

[5, 2] [7, 6, 4, 1] [3]

Next, reverse each array:

[2, 5] [1, 4, 6, 7] [3]

Finally, concatenate them all together:

[2, 5, 1, 4, 6, 7, 3]

This should be what your program outputs/function returns. Repeat this procedure enough times and the array will be fully sorted.

Rules

• Input and output may be given through any standard methods, and may be in any reasonable array format.
• The input array will never be empty, but may contain negatives and/or duplicates.
• The absolute value of each integer will always be less than 2³¹.

Test cases

Hopefully these cover all edge cases:

[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

Scoring

This is code-golf, so the shortest code in bytes wins.

Answer 1

JavaScript (ES6), 64 bytes

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

Recursion FTW! The basic algorithm in use here is to keep track of the current non-ascending run in an array, "returning" it whenever an ascending element is found. We do this recursively, continually concatenating the results, until we run out of items. By creating each run in reverse ([n,...z] instead of [...z,n]), we can avoid the lengthy .reverse() at no cost.

Test snippet

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

g=a=>console.log("Input:",`[${a}]`,"Output:",`[${f(a)}]`)

g([1])
g([1,1])
g([1,2])
g([2,1])
g([3,2,1])
g([3,1,2])
g([3,1,1,2])
g([5,2,7,6,4,1,3])

<input id=I value="5, 2, 7, 6, 4, 1, 3">
<button onclick="g((I.value.match(/\d+/g)||[]).map(Number))">Run</button>

Answer 2

Python 3, 63 bytes

f=lambda x,*p:x[:1]>p>()and p+f(x)or x and f(x[1:],x[0],*p)or p

Try it online!

Answer 3

JavaScript (ES6), 70 bytes

Sure, this is already beaten by ETHproductions answer, but that's the best I could come up with so far without using recursion.

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

Note: Initializing both r and o to the exact same object with r = o = [] may look like a hazardous idea. But it is safe to do so here because r is immediately assigned its own instance (containing the first element of a) on the first iteration with r = [n, ...r].

Test cases

let f =

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([2, 1])));
console.log(JSON.stringify(f([2, 3, 1])));
console.log(JSON.stringify(f([2, 1, 3])));
console.log(JSON.stringify(f([2, 1, 2])));
console.log(JSON.stringify(f([2, 1, 1])));
console.log(JSON.stringify(f([3, 1, 1, 2])));
console.log(JSON.stringify(f([3, 2, 1, 2])));
console.log(JSON.stringify(f([3, 1, 2, 2])));
console.log(JSON.stringify(f([1, 3, 2, 2])));
console.log(JSON.stringify(f([1, 0, 5, -234])));
console.log(JSON.stringify(f([1, 0, 1, 0, 1])));
console.log(JSON.stringify(f([1, 2, 3, 4, 5])));
console.log(JSON.stringify(f([5, 4, 3, 2, 1])));
console.log(JSON.stringify(f([2, 1, 5, 4, 3])));
console.log(JSON.stringify(f([2, 3, 1, 5, 4])));
console.log(JSON.stringify(f([5, 1, 4, 2, 3])));
console.log(JSON.stringify(f([5, 2, 7, 6, 4, 1, 3])));
console.log(JSON.stringify(f([-5, -2, -7, -6, -4, -1, -3])));
console.log(JSON.stringify(f([14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9])));

Answer 4

Jelly, 8 bytes

Ṁ;<œṗ³UF

Try it online!

Explanation:

Ṁ;         Prepend the list [a1, a2… an] with its maximum.
  <        Elementwise compare this with the original list:
           [max(a) < a1, a1 < a2, …, a(n-1) < an, an]
           The first element is always 0.
   œṗ³     Partition the original list (³) at the indices
           of the non-zero values in the working list.
           (The spurious `an` at the end of the left argument,
           resulting from comparing lists of different sizes,
           is ignored by this operation, thankfully.)
      U    Reverse each part.
       F   Flatten.

Answer 5

MATL, 15 bytes

lidO>vYsGhXSOZ)

Input is a column vector, with the format [5; 2; 7; 6; 4; 1; 3] (semicolon is the row separator).

Try it online!

Take input [5; 2; 7; 6; 4; 1; 3] as an example.

Explanation

l     % Push 1
      % STACK: 1
i     % Push input
      % STACK: 1, [5; 2; 7; 6; 4; 1; 3]
d     % Consecutive differences
      % STACK: 1, [-3; 5; -1; -2; -3; 2]
O>    % Test if greater than 0, element-wise
      % STACK: 1, [0; 1; 0; 0; 0; 1]
v     % Concatenate vertically
      % STACK: [1; 0; 1; 0; 0; 0; 1]
Ys    % Cumulative sum
      % STACK: [1; 1; 2; 2; 2; 2; 3]
G     % Push input again
      % STACK: [1; 1; 2; 2; 2; 2; 3], [5; 2; 7; 6; 4; 1; 3]
h     % Concatenate horizontally
      % STACK: [1 5; 1 2; 2 7; 2 6; 2 4; 2 1; 3 3]
XS    % Sort rows in lexicographical order
      % STACK: [1 2; 1 5; 2 1; 2 4; 2 6; 2 7; 3 3]
OZ)   % Get last column. Implicitly display
      % STACK: [2; 5; 1; 4; 6; 7; 3]

Answer 6

Mathematica, 30 27 bytes

^{3 bytes saved due to @Martin Ender.}

Join@@Sort/@Split[#,#>#2&]&

Anonymous function. Takes a list of numbers as input and returns a list of numbers as output.

Answer 7

Python 2, 100 bytes

A really terrible golf, but I wanted to post my solution (one does not simply outgolf Dennis)...

d=input();L=[];x=0;d+=-~d[-1],
for i in range(1,len(d)):
 if d[i]>d[i-1]:L+=d[x:i][::-1];x=i
print L

Test on repl.it!

Input should be given as a Python list literal, such as [5, 3, 4, 2, 6, 1].

The basic idea is to make heavy use of Python's slicing syntax, slicing each necessary section from the array, reversing it, and adding it to the new array.

Answer 8

05AB1E, 19 18 16 14 bytes

Saved 2 bytes using Luis Mendo's sorting trick

ü‹X¸ì.pO¹)ø{ø¤

Try it online!

Explanation

Example input [5, 2, 7, 6, 4, 1, 3]

ü‹               # pair-wise less-than
                 # STACK: [0, 1, 0, 0, 0, 1]
  X¸ì            # prepend a 1
                 # STACK: [1, 0, 1, 0, 0, 0, 1]
     .p          # prefixes
       O         # sum
                 # STACK: [1, 1, 2, 2, 2, 2, 3]
        ¹        # push input
                 # STACK: [1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]
         )       # wrap stack in list
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]]
          ø      # zip
                 # STACK: [[1, 5], [1, 2], [2, 7], [2, 6], [2, 4], [2, 1], [3, 3]]
           {     # sort
                 # STACK: [[1, 2], [1, 5], [2, 1], [2, 4], [2, 6], [2, 7], [3, 3]]
            ø    # zip
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [2, 5, 1, 4, 6, 7, 3]]
             ¤   # tail
                 # OUTPUT: [2, 5, 1, 4, 6, 7, 3]

Previous 16 byte solution

Dü‹X¸ì.pO.¡€g£í˜

Answer 9

Pyke, 11 8 bytes (old version)

$0m<fm_s

Try it here! (works on latest version)

$        -     delta(input)
 0m<     -    map(i<0 for i in ^)
    f    -   split_at(input, ^)
     m_  -  map(reverse, ^)
       s - sum(^)

Answer 10

JavaScript (ECMA 6), 121 128 125 119 108 bytes

f=a=>{p=a[0],c=[],b=[];for(e of a){e>p&&b.push(c.reverse(c=[]));c.push(p=e)}return[].concat.call([],...b,c)}

Lambda expression takes a single Array parameter, a.

Thanks to @ETHproductions for helping me see my first mistake.

Answer 11

Retina, 163 bytes

Yes, I know how horrid this is. Supporting zeros and negatives was super fun. Byte count assumes ISO 8859-1 encoding.

\d+
$*
(?<=-1*)1
x
-

x,1
x¶1
\b(1+),(1+\1)\b
$1¶$2
,,1
,¶1
x,(¶|$)
x¶¶
(?<=\b\1x+(?=,(x+))),\b
¶
O%$#`.(?=(.*))
$.1
+`¶
,
\bx
-x
(\w+)
$.1
^,
0,
,$
,0
,,
,0,
^$
0

Try it online

Explanation:

\d+                         # Convert to unary
$*
(?<=-1*)1                   # Replace negatives with x's instead of 1's
x
-                           # Remove minus sign

x,1                         # Separate if negative before positive
x¶1
\b(1+),(1+\1)\b             # or greater positive follows a positive
$1¶$2
,,1                         # or positive follows a zero
,¶1
x,(¶|$)                     # or zero follows a negative
x¶¶
(?<=\b\1x+(?=,(x+))),\b     # or negative follows a negative of greater magnitude.
¶
O%$#`.(?=(.*))              # Swear at the input, then reverse each line
$.1
+`¶                         # Remove breaks, putting commas back
,
\bx                         # Put the minus signs back
-x
(\w+)                       # Replace unary with length of match (decimal)
$.1
^,                          # Do a bunch of replacements to resurrect lost zeros
0,
,$
,0
,,
,0,
^$
0

Answer 12

Ruby, 60 55 bytes

s=->x{x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten} 

Pretty much what the challenge asked for. I defined a lambda s, that takes an array x, and sever (slices) it into smaller pieces where the following element would be greater than. This gives back an enumerator, which we can call map on and reverse the order of the pieces, before finally bringing it all together with flatten, which concatenates the elements in the defined order into one array.

Tests

p s[[1]]===[1]
p s[[1, 1]]===[1, 1]
p s[[1, 2]]===[1, 2]
p s[[2, 1]]===[1, 2]
p s[[2, 3, 1]]===[2, 1, 3]
p s[[2, 1, 3]]===[1, 2, 3]
p s[[2, 1, 2]]===[1, 2, 2]
p s[[2, 1, 1]]===[1, 1, 2]
p s[[3, 1, 1, 2]]===[1, 1, 3, 2]
p s[[3, 2, 1, 2]]===[1, 2, 3, 2]
p s[[3, 1, 2, 2]]===[1, 3, 2, 2]
p s[[1, 3, 2, 2]]===[1, 2, 2, 3]
p s[[1, 0, 5, -234]]===[0, 1, -234, 5]
p s[[1, 0, 1, 0, 1]]===[0, 1, 0, 1, 1]
p s[[1, 2, 3, 4, 5]]===[1, 2, 3, 4, 5]
p s[[5, 4, 3, 2, 1]]===[1, 2, 3, 4, 5]
p s[[2, 1, 5, 4, 3]]===[1, 2, 3, 4, 5]
p s[[2, 3, 1, 5, 4]]===[2, 1, 3, 4, 5]
p s[[5, 1, 4, 2, 3]]===[1, 5, 2, 4, 3]
p s[[5, 2, 7, 6, 4, 1, 3]]===[2, 5, 1, 4, 6, 7, 3]
p s[[-5, -2, -7, -6, -4, -1, -3]]===[-5, -7, -2, -6, -4, -3, -1]
p s[[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9]]===[3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

Answer 13

Brachylog, 10 bytes

~c:{>=r}ac

Try it online!

Explanation

~c            Deconcatenate the Input
  :{>=r}a     Each resulting sublist must be non-increasing, and then reverse it
         c    Concatenate

Answer 14

Dyalog APL, 7 15 bytes

Requires ⎕ML←3, which is default on many systems.*

{∊⌽¨⍵⊂⍨1+⍵-⌊/⍵}

∊ enlist (flatten)

⌽¨ each-reversed

⍵⊂⍨ the argument partitioned* by cutting where each corresponding element is larger than its predecessor in

1+ one plus

⍵- the argument minus

⌊/⍵ the smallest element of the argument

---

Old 7 byte solution fails with non-positive integers:

Requires ⎕ML←3, which is default on many systems.*

∊⌽¨⊆⍨⎕

∊ enlist (flatten) the

⌽¨ each-reversed

⊂⍨ self-partitioned*

---

* Partition (⊂) is a function which cuts its right argument where the corresponding left argument is larger than the preceding one. (Unfortunately it only accepts non-negative integers, and zero has special meaning.) From version 16, this functionality of ⊂ is available on all systems (even those where ⎕ML≠3), using the glyph ⊆.

Answer 15

Haskell, 49 bytes

(a:b)%l|any(<a)l=l++b%[a]|1<2=b%(a:l)
_%l=l
(%[])

Usage example: (%[]) [5,2,7,6,4,1,3] -> [2,5,1,4,6,7,3].

Recursive approach. The function % takes the input list as its first parameter and an accumulator l which keeps track of the non-ascending chunk so far (in reverse order). The base case is reached when the input list is empty and then the result is the accumulator. If the input list is not empty and the first element a doesn't fit in the current chunk (any(<a)l), return the accumulator and append a recursive call on the rest of the list and a as the new accumulator (l++b%[a]). Else, make a recursive call on the rest of the list and a prepended to tha accumulator (b%(a:l)). The main function (%[]) calls % with an empty accumulator.

Answer 16

R, 64 bytes

cat(unlist(lapply(split(x<-scan(),cumsum(c(F,diff(x)>0))),rev)))

Reads input from stdin. We split the input into a list of vectors using split() which requires a factor variable that groups the input. The factor is created by taking the cumulative sum of the the logical vector for which the difference is positive.

Consider the vector:

x=c(5, 2, 7, 6, 4, 1, 3)

Now taking the difference and prepending F by running y=c(F,diff(x)>0) would produce the following logical vector:

[1] FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE

Taking the cumulative sum cumsum(y) produces a vector where each group is represented by a unique factor upon which we can combine with the split function:

[1] 0 0 1 1 1 1 2

Answer 17

Retina, 98 bytes

Byte count assumes ISO 8859-1 encoding.

$

-(\d+)
$1$*-/
\d+
$*
S-`(?<=(-+)/ )(?!\1)|(?=\b(1+))(?<!\2 )
O%`\S* 
¶

((-)|1)*/? 
$2$#1 
 $

Try it online!

Answer 18

Octave, 75 44 bytes

Based on MATL answer of @LuisMendo

@(a)sortrows([cumsum([1;diff(a)>0]),a])(:,2)

Try it Online!

Previous answer

@(a)[fliplr(mat2cell(f=fliplr(a),1,diff(find([1,diff(f)<0,numel(a)])))){:}]

Try it Online!

reverse the array

f=fliplr(a)

take first difference of f

d = diff(f);

find position of where the next element is less than the previous element

p=find([1,diff(f)<0,numel(a)])

first difference of the positions returns length of each sub array

len=diff(p)

use length of each sub array in mat2cell to split the array to nested list of arrays

nest = mat2cell(f,1,len);

reverse the nested list

rev_nest = fliplr(nest) 

flatten the nested list

[rev_nest{:}]

Answer 19

Pyth - 15 bytes

s_McQf<@QtT@QTU

Try it online here.

Answer 20

Perl 6, 59 bytes

{map |+«*.[0].reverse,m/:s([(\-?\d+)<?{[>=] $0}>] +)+/[0]}

Regex-based solution.
Because this is Sparta Perl!!

• m/ /: Stringify the input array, and match a regex against it.
• (\-? \d+): Match a number, and capture it as $0.
• <?{ [>=] $0 }>: Zero-width assertion that only matches if all $0 captured so far in the current sub-match are in non-ascending order.
• ([ ] +)+: Repeat the last two steps as often as possible, otherwise start a new sub-match.
• map , [0]: Iterate over the sub-matches.
• |+«*.[0].reverse: For each one, take the list of values matched by $0, reverse it, coerce the values to numbers (+«), and slip them into the outer list (|).

Perl 6, 63 bytes

sub f(\a){flat $_,f a[+$_..*]with first {[<=] $_},:end,[\R,] a}

Recursive list processing solution.
More laborious than I had hoped.
Even though the language has lots of convenient built-ins, there seem to be none for list partitioning (e.g. like Ruby's slice_when or Haskell's takeWhile).

Answer 21

Stacked, noncompeting, 34 bytes

Still constantly developing this language.

{e.b:e b last<}chunkby$revmap flat

Argument lies on TOS. Try it here!

chunkby takes a function and collects arrays of contiguous data that satisfy the function. The function then is:

{e.b:e b last<}
{e.b:         }  function with arguments [e, <unused>, b]--the element, <the index>, and the
                 chunk being built
     e       <   check if e is less than
       b last    the last element of b

This gives a strictly decreasing array.

$revmap is basically [rev]map and reverses each item.

flat finally flattens the array.

---

Some fun for actually sorting the array:

[{e.b:e b last<}chunkby$revmap flat] @:sortstep
[$sortstep periodloop] @:sort

10:> @arr
arr out
arr shuf @arr
arr out
arr sort out

This outputs (for example):

(0 1 2 3 4 5 6 7 8 9)
(4 5 1 0 6 7 2 8 9 3)
(0 1 2 3 4 5 6 7 8 9)

Answer 22

Python, 151 139 Bytes

Saved 12 Bytes thanks to @Flp.Tkc!

Nowhere near @Flp.Tkc, let alone...

def s(l):
 r=[];i=j=0
 while j<len(l)-1:
  if l[j+1]>l[j]:r+=l[i:j+1][::-1],;i=j+1
  j+=1
 r+=l[i:j+1][::-1],;return[i for s in r for i in s]

Answer 23

Python 2, 74 bytes

b=[];c=[];a+=9e9,
for i in a[:-1]:
 b=[a.pop(0)]+b
 if b[0]<a[0]:c+=b;b=[]

Input in a, output in c

Answer 24

Python 3, 191 Bytes

a=[int(i)for i in input().split()]
while a!=sorted(a):
 b=[[]]
 for i,j in enumerate(a):
  if a[i-1]<j:b+=[[j]]
  else:b[-1]+=[j]
 a=[]
 for l in[k[::-1]for k in b]:a+=[k for k in l]
print(a)

I'm not sure if using the sorted function to check is allowed here, but I couldn't think of a good reason against it, and it brought down my byte count by ~30 Bytes.

Answer 25

Clojure, 105 bytes

#(filter number?(mapcat reverse(partition-by not(mapcat(fn[[a b]][a(< b a)])(partition 2 1(conj % 1))))))

Partitions into pairs on consecutive numbers, puts true or false between them, partitions on not to true and numbers become false and false true, reverses partitions and keeps numerical values.