49
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
7
  • 4
    \$\begingroup\$ What's the big-o of this sorting method? \$\endgroup\$ Commented Dec 21, 2016 at 22:08
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ Commented Dec 21, 2016 at 22:23
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ Commented Dec 21, 2016 at 22:45
  • 2
    \$\begingroup\$ @WheatWizard reversing an array doesn't require room for a copy of the array, only room for a single element. and is O(n). swap first and last elements then swap second and second last elements etc, when you get to the middle stop. \$\endgroup\$ Commented Dec 22, 2016 at 11:27
  • \$\begingroup\$ Reversing is O(n), but reversing can be built right into the algorithm (that's what my JS answer does); since each iteration loops over each item in the array once, a single iteration is O(n). (I think...) \$\endgroup\$ Commented Dec 22, 2016 at 14:27

35 Answers 35

Reset to default
1
2
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 54 bytes

x=>x.map((t,i)=>z.splice(q=t<=x[i-1]?q:i,0,t),z=[])&&z

Try it online!

Recurseless win

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=reduce -ap, 45 bytes

$_=reduce{$a<$b&&(print$a,$")&&$b||"$b $a"}@F

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Go, 172 bytes

func(s[]int)(o[]int){if len(s)<2{return s}
a:=[]int{s[0]}
for _,e:=range s[1:]{if a[0]<e{o,a=append(o,a...),[]int{e}}else{a=append([]int{e},a...)}}
o=append(o,a...)
return}

Attempt This Online!

Explanation

func(s[]int)(o[]int){
if len(s)<2{return s}            // return the original if it's 1 element or smaller
a:=[]int{s[0]}                   // seed with the first element
for _,e:=range s[1:]{            // for each element of the tail...
 if a[0]<e{                      // if the previous element was smaller than the current...
  o,a=append(o,a...),[]int{e}    // append to the output, and reset
 }else{a=append([]int{e},a...)}} // otherwise push to the front
o=append(o,a...)                 // append the remainder to the output
return}                          // return
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Japt, 5 bytes

ò< cw

Try it

ò      Partition between elements A, B where the following is true:
 <       A < B
   c   Flatten after mapping each list to:
    w    it reversed
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Replace m with c to get the correct output. \$\endgroup\$ Commented Jan 29, 2024 at 22:57
  • \$\begingroup\$ @Shaggy Forgot about that, nice idea \$\endgroup\$ Commented Jan 30, 2024 at 1:43
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.