Pseudosort a list in 2*n comparisons

Question

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.

Answer 1

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

Answer 2

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.