# 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, 2014 at 10:52
• Wait, the last two bonuses are incompatible! Jan 12, 2014 at 11:21
• What about lists that have no "alternating solution"?--e.g.{2,1,9,9,9,9,9,9,9}. Jan 12, 2014 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. Jan 12, 2014 at 13:59
• @MvG Either function or filter is fine by me. Jan 12, 2014 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. Jan 12, 2014 at 17:25 # 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. Feb 12, 2014 at 20:32 • Also Length@_x works too, a bit clearer with same length. Feb 12, 2014 at 21:40 # 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}  # 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  # 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. Jan 12, 2014 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, 2014 at 13:42 • I only recently discovered how useful map is. Thanks for the help! Feb 12, 2014 at 18:40 # 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! # 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)  # 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 # Vyxal, 18 - 40 = -22 bytes Ṗ'¯±:k+$•⁼;:?c[_|℅


Try it Online!

This is why bonuses are a bad idea

## 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)
`