Alternating sort

Question

Given a list of pairwise distinct integers, sort it in alternating order: The second number is larger than the first, the third is smaller than the second, the fourth is larger than the third etc. (This order is not unique.) E.g., 5 7 3 4 2 9 1 would be valid output.

Extra points (since this is code golf, subtract from the number of characters):

• 15 for not using any built-in sort functionality.
• 15 if your code does not reorder inputs that are already ordered this way.
• 10 if the output order is random, i.e., multiple runs with the same input yield different correct outputs.

Answer 1

Golfscript, 21-30 = -9

~(\{.2$>0!:0^{\}*}/]`

Bonuses: does not use built-in sort constructs (-15); does not modify a sorted array (-15)

Since, in general, it's not possible to sort an array of integers as defined, this assumes that either all integers are distinct, or "larger" and "smaller" actually mean "or equal".

Explanation:

Algorithm taken from Stack Overflow:
What is the most efficient way to sort a number list into alternating low-high-low sequences?

• ~(\ evals the input, which should yield an array, pops the first element and swaps it before the array.
• {...}/]` iterates the block over the array, collecting the results on the stack so that they can be reused immediately, then collects them into an array and stringifies the array so that it's displayed in a sensible format.

The block:

• .2$> duplicates top two elements of the stack (in reverse order) and compares them, yielding 0 or 1.
• 0!:0 pushes an negates a zero, then overwrites zero with its negated version. This, the variable 0 alternates between the values 0 and 1. This is used to define the comparison sense. It's nice to have a variable initialised to the logical zero, and 0 just happens to be a variable and initialised to the value of 0.
• ^{\}* XORS the sense with the comparison result, then swaps the top two elements if the result is true.

Example:

;"[3 8 1 6 5 4 7 2 9]"
~(\{.2$>0!:0^{\}*}/]`
#[3 8 1 6 4 7 2 9 5]

Answer 2

Mathematica 24 19 18 = 58 - 40

u = {1, 4, 9, 2, 7, 5, 3, 8, 6}    

u//.s:{x___,y_,z_,___}/;y>z⊻OddQ@Tr[1^{x}]:>RandomSample@s

{4, 5, 3, 8, 2, 7, 1, 9, 6}

It doesn't reorder ordered list.

For a list with an even number of elements one can save 2 characters:

n=0;u//.s:{x___,y_,z_,___}/;OddQ@n++⊻y>z:>RandomSample@s

Answer 3

Mathematica 81-15-15-10=41

f[t_] := t //. {l___, x_, y_, z_, r___} /; x > y > z || x < y < z :> 
   f@RandomSample[s = {l, x, z, y, r}] /; s != t

Examples

f@{1, 2, 3, 4, 5, 6, 7, 8}
> {1, 4, 3, 6, 5, 7, 2, 8}

f@{1, 2, 3, 4, 5, 6, 7, 8}
> {8, 3, 5, 2, 7, 4, 6, 1}

f@{8, 3, 5, 2, 7, 4, 6, 1}
> {8, 3, 5, 2, 7, 4, 6, 1}

Answer 4

Japt, 19-40 = -21 bytes

äÎäÎשUªá fÈäÎäÎ×Ãö

Try it

äÎäÎשUªá fÈäÎäÎ×Ãö     :Implicit input of array U
ä                       :Consecutive pairs
 Î                      :  Signs of differences
  äÎ                    :As above
    ×                   :Reduce by multiplication
     ©U                 :Logical AND with U
       ª                :Logical OR with
        á               :  Permutations of U
          f             :  Filter by
           È            :  Passing each through the following function
            äÎäÎ×       :    As above
                 Ã      :  End filter
                  ö     :  Random element

w/o Bonuses, 9 bytes

á æÈäÎäÎ×

Try it

á æÈäÎäÎ×     :Implicit input of array
á             :Permutations
  æ           :First element to return true when
   È          :Passed through the following function
    äÎäÎ×     :  As above

Answer 5

C (57 = 97 characters - 40 bonus)

i,t,j;f(a[],n){for(;++i<n;)if(a[i^i&1]>a[i^!i&1])for(i=n;--i;)t=a[j=rand()%n],a[j]=a[i],a[i]=t;}

Bogosort with alternating compares shuffling with Fisher-Yates. The shuffle loop uses the same index as the comparison loop so when the shuffle is done the comparison loop is automatically reset. The indexes in the array we compare have their lowest bit flipped based on the index we compare, it works without parentheses thanks to nice operator precedence and associativity.

Assumes that rand is actually random or at least seeded properly.

Answer 6

Ruby 1.9+ (20 = 35 characters - 15 bonus)

Ah, the good ol' minmax!

f=->a{a[1]&&(m=a.minmax)+f[a-m]||a}

Sample run:

irb(main):004:0> f[[1,2,3,4,5,6,7]]
=> [1, 7, 2, 6, 3, 5, 4]

Ruby 1.9+ (43 = 83 characters - 40 bonus)

A solution that satisfies all the bonuses: Shuffles the argument array until it's alternatingly (?) sorted. To check the array, it is zipped toghether with a shifted copy of itself and an alternating array of < and > symbols, forming something like [[1, :<, 2], [2, :>, 3], [3, :<, 4], [4, :>, 5], ... ]

f=->a{a.shuffle!until a.zip([:<,:>].cycle,a[1..-1]).all?{|x,o,y|!y||x.send(o,y)};a}

Answer 7

Python (75 = 115 characters - 40 bonus)

The same strategy as the second entry in my Ruby answer, except it loops on while instead of until and the condition is negated (from "all correct" to "any uncorrect").

from random import*
def f(a):
 while any(eval(`x`+o+`y`)for x,y,o in zip(a,a[1:],"><"*len(a))):shuffle(a)
 return a

Answer 8

This is my first ever code golfing attempt. Not sure how happy I am with it (there must be a better way to get list of each character in stdin than raw_input() and a list comprehension) but for a first try I think I'm proud.

Python 2.7 (117 = 117 chars - 0 bonuses)

def f(l):
 o=[]
 l.sort()
 while len(l):o.append(l.pop(0));l=l[::-1]
 return o
print f(map(int,raw_input().split()))

Answer 9

JavaScript (Node.js), 75-40=35 bytes

f=x=>x.some((c,i)=>c>x[i-1]^i%2)?f(x,x.splice(Math.random()*2,0,x.pop())):x

Try it online!

Answer 10

Python 3 (119 = 159 chars - 40 bonuses)

def o(x):
 a,s=x[0],1
 for b in x[1:]:
  if(b-a)*s<0:return 1
  s,a=-s,b
import random
s=list(map(int,input().split()))
while o(s):random.shuffle(s)
print(*s)

Answer 11

Python 3 (may be 2 also)

def f(a):
 for i in range(len(a)-1):
  if (a[i+1]-a[i])*(-1)**i<0:
   a[i:i+2]=a[i+1],a[i]
 return a

100 characters (100)
Do not used builting sorting (-15)
Do not moved already alternating values (-15)
O(n) time complexity (-0)
Total score = 100 - 15 - 15 - 0 = 70

Answer 12

Vyxal, 18 - 40 = -22 bytes

Ṗ'¯±:k+$•⁼;:?c[_|℅

Try it Online!

This is why bonuses are a bad idea

Answer 13

JavaScript, 87

Fairly straightforward approach: sort given array in ascending order, then swap every two elements starting with the second one ([a[i],a[i+1]]=[a[i+1],a[i]]).

According to author, function is OK, so here's a function (87 characters):

function s(a){a.sort();for(i=1;i<a.length-1;[a[i],a[i+1]]=[a[i+1],a[i]],i+=2);return a}

Version with I/O (94 characters, you are supposed to type array like this: 3,7,9,2,1,4,5):

a=(prompt().split(",")).sort();for(i=1;i<a.length-1;[a[i],a[i+1]]=[a[i+1],a[i]],i+=2);alert(a)