Alternating sort

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.
• Do we write a stand-alone program, reading from stdin and writing to stdout, or rather a function, accepting a sequence as an argument and returning the modified sequence? Or may we choose either? – MvG Jan 12 '14 at 10:52
• Wait, the last two bonuses are incompatible! – John Dvorak Jan 12 '14 at 11:21
• What about lists that have no "alternating solution"?--e.g.{2,1,9,9,9,9,9,9,9}. – DavidC Jan 12 '14 at 13:34
• Although the task as specified isn't exactly a duplicate of The Strange Unsorting Machine for Nefarious Purposes, many of the answers there are applicable so it doesn't add much to the site. – Peter Taylor Jan 12 '14 at 13:59
• @MvG Either function or filter is fine by me. – Christopher Creutzig Jan 12 '14 at 17:11

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]

• I wish I had seen the SO question. That really makes this whole question uninteresting. – Christopher Creutzig Jan 12 '14 at 17:25
• +1 for 0!:0.​ – Ilmari Karonen Jan 12 '14 at 20:41

Mathematica 2419 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

• You can write even test as 2\[Divides] instead of OddQ@ which is 3 characters shorter, replacing > with < to restore order. – swish Feb 12 '14 at 20:32
• Also Length@_x works too, a bit clearer with same length. – swish Feb 12 '14 at 21:40

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.

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}


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


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

• Welcome to Programming Puzzles & Code Golf Stack Exchange! "Given a list of integers, sort it in alternating order:" - you seem to be sorting the characters of the input instead. – John Dvorak Jan 12 '14 at 13:29
• Use built in map() to take input. You can use it this way map(int,raw_input().split()) This will return a list of integers. – Wasi Jan 12 '14 at 13:42
• I only recently discovered how useful map is. Thanks for the help! – undergroundmonorail Feb 12 '14 at 18:40

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)


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)


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

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}
`