Pseudosort a list in 2*n comparisons

Write a program that takes a list of n space-separated integers, and outputs a permutation of that list using a maximum of 2*n comparisons.

It should loop this until an empty line is input. Alternatively, it can accept inputs until an empty line is given, then output all the permutations.

Though your program only has to work on integers, it should be possible to implement your algorithm for any comparable data structures. For example, using sign(a-b) to get extra comparisons is illegal, because the same algorithm can't be applied to data structures without numerical values.

Example session:

>0 1 2 3 4
0 1 2 3 4
>7 9 2 1
1 2 7 9
>6 7 4 5 2 3 0 1
0 2 3 1 4 5 6 7
>


or

>0 1 2 3 4
>7 9 2 1
>6 7 4 5 2 3 0 1
>
0 1 2 3 4
1 2 7 9
0 2 3 1 4 5 6 7


note: > shouldn't actually be printed, it's just being used to notate input vs output.

Scoring

Scoring is based mostly on how well sorted the permutations are, but also favours concise code.

Run your program with this file as input. Use your program's output as input to this python script. This script works under both python 2.7 and 3.3. Other versions weren't tested.

import sys
def score(l):
n = len(l)
w = n**2 // 2
s = sum(abs(l[i]-i)for i in range(n))
return float(s)/w
s = 0.0
for i in range(40000):
s += score([int(n) for n in sys.stdin.readline().split()])
print (int(s))


Your score is the output of the above script plus the length of your program

Explanation of Scoring

In the input file, there are 1000 lists for each length n in the range 10 <= n < 50. In total, there are 40000 lists. No two elements of a list will be equal.

To score a list, we define the unsortedness of a list as the sum of distances of each element from where it should be. For example, for the list [0,1,4,3,2], the unsortedness is 4, because 4 and 2 are each 2 positions from where they should be, and the rest of the numbers are correct.

The worst case unsortedness of a list of length n is n^2 / 2, using integer division.

The score of a list is its unsortednes divided by the maximum unsortedness. This is a number between 0.0 (sorted) and 1.0 (reversed).

Your total score is the sum of all scores in the input rounded down to an integer, plus the length of your program. Because there are 40000 cases, a better pseudo-sort is likely better than shorter code, but if there is some optimal solution, then the shortest implementation of that solution will win.

• Can we use bit manipulation functions? We can't assume that (x-y) is defined, but what about (x & ~y)? Dec 4 '12 at 18:21
• "It should be possible to implement your algorithm for any comparable data structures", so no. Dec 4 '12 at 18:53
• Well, I figured that wasn't what you wanted. But I'm pretty sure any data structure can be represented in binary. :) Dec 4 '12 at 18:55
• Yes, but the comparison of binary representations isn't necessarily the same as how comparisons are defined for the structure. Dec 4 '12 at 19:00
• Right. Don't know what I was thinking. Dec 4 '12 at 19:46

Python, 7910 (7704 + 206)

This was inspired by shell sort. I found relatively good coefficients for the gap sequence (g) by checking a few hundred alternatives. The number of comparisons is limited by counting explicitly (n).

s=1
while s:
s=map(int,raw_input().split());k=len(s);n=2*k;g=13*k/23
while g:
for i in range(g,k):
n-=1
if n<0:break
if s[i]<s[i-g]:s[i],s[i-g]=s[i-g],s[i]
g=3*g/5
print' '.join(map(str,s))

• I started implementing a combsort, until I realized that's exactly what your solution is. I was able to get a best score of 7428 by tweaking a few constants: codepad.org/mla6qDlN. The problem with using integer division for your gaps, is that it will decrease more quickly than it should. Dec 8 '12 at 5:47
• @primo: Ok, I hadn't heard about comb sort before. It seems that you can get a better score than my current one with integer division too...
– han
Dec 8 '12 at 9:21
• Indeed you can. Take your code, exactly as written, and replace g=13*k/23 with g=28 for a score of 7541. This will allow it to always take the same path downwards. [28, 16, 9, 5, 3, 1], which seems to be the best for the mutliplier you're using. Dec 8 '12 at 9:39
• Scratch that. Start with g=16 instead for 7449. Dec 8 '12 at 10:07
• @primo: I'll leave the solution as is for now, since starting with a constant would no longer feel like a solution to the general problem. But thanks for all the improvements!
– han
Dec 9 '12 at 13:16

Ruby, 10140 (9988 + 152)

def q a
p=a.pop
l,m=a.partition{|x|x<p}
[l,p,m]
end
while a=gets
a=a.split.map(&:to_i)
l,p,m=q a
puts (q(l)+[p]+q(m)).flatten.join(" ")
end


This simply performs two rounds of quicksort. It removes the last element, then divides the remaining array into those less than and those greater than that element (n-1 comparisons). Then it does the same thing to those two (n-3 comparisons) and joins the result in order. Total comparisons are 2*n - 4 (worst case 2*n - 2), so there's definitely room for improvement.