Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 231.

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

share|improve this question
3  
What's the big-o of this sorting method? – mbomb007 13 hours ago
    
@mbomb007 I don't understand big-o notation very well, but I think a single iteration is O(n). Multiply that by worst-case n iterations and you get O(n^2) (worst-case; best-case would be O(n), I think, for a single iteration). – ETHproductions 12 hours ago
    
That sounds right to me, however it's worth pointing out that reversing an array isn't a very efficient operation, so it's a slow O(n^2) – DJMcMayhem 12 hours ago
1  
@DJMcMayhem Reversing can be done in O(n) but requires O(n) memory. O(n^2) is the best with O(1) memory. – Wheat Wizard 7 hours ago

17 Answers 17

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>

share|improve this answer
    
Can you explain how your array gets parsed into your first parameter [n,...a]. What is n? Is that just the first item in your array? – obarakon 11 hours ago
1  
@obarakon Correct. n is the first item in the array, and a is the rest of the array. You can find more info here. – ETHproductions 11 hours ago
    
Thank you. That was very helpful. Since your first parameter is an array, why do you need to include the ...a? Is that just so you can take advantage of n? One more thing, when you call f(a,q), does q get set to the parameter z? – obarakon 11 hours ago
    
@obarakon Well, f=([n])=>... would only capture the first element, and f=([n,a])=>... would capture only the first in n and the second in a. Another way to do what f=([n,...a])=>,,, does would be f=a=>(n=a.unshift(),.... – ETHproductions 6 hours ago
    
And since z is the second parameter in the function, when f(a,q) is called, f sees it as z. Hope this helps! – ETHproductions 6 hours ago

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

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])));

share|improve this answer
1  
No worries, I love seeing different approaches. And one often ends up becoming shorter than another after golfing :-) – ETHproductions 12 hours ago

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]
share|improve this answer

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.
share|improve this answer
1  
I was on the verge of hitting Save Edits when I saw your answer... Well done. – Dennis 11 hours ago
    
@Dennis Heh, so you added Dyalog partitioned enclose, but what about APL2 partition? – Adám 2 hours ago

Python, 63 bytes

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

Try it online!

share|improve this answer

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£í˜
share|improve this answer
    
Those linebreaks explained it wonderfully... :-P – Stewie Griffin 12 hours ago
    
@StewieGriffin: Yeah, I changed up the code and posted before I had rewritten the explanation :P – Emigna 12 hours ago

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.

share|improve this answer
1  
Welcome to PPCG! Are you sure this works, though? f=a=>p=a[0] is a single expression; to include more, you'd need to wrap the body of the function in braces or parentheses. – ETHproductions 12 hours ago
    
Nice! I think you can do return(b+","+c).split`,` to save a few bytes at the end. – ETHproductions 11 hours ago
    
Better yet, you can use c.unshift instead of c.push to remove the need to reverse c. After doing this, I got 94 bytes. – ETHproductions 11 hours ago

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
share|improve this answer

Ruby, 60 bytes

def s x;x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten;end

Pretty much what the challenge asked for. I defined a function 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]
share|improve this answer
    
Welcome, nice <s>first</s> second answer, check this: codegolf.stackexchange.com/questions/363/… – G B 2 hours ago

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!

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.

share|improve this answer
    
I think the first line can be d,L,x=input(),[],0;d+=.... – Dopapp 5 hours ago
    
@Dopapp that's exactly the same byte count – Flp.Tkc 4 hours ago

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(^)
share|improve this answer

Mathematica, 30 bytes

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

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

share|improve this answer

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
share|improve this answer

Pyth - 15 bytes

s_McQf<@QtT@QTU

Try it online here.

share|improve this answer

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).

share|improve this answer

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)
share|improve this answer

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 .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.