Return to Answer

shave off one character

Source Link

edited Dec 6, 2012 at 12:08

1.2k
8
10

Python, 79117910 (7704 + 207206)

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=6*gg=3*g/105
 print' '.join(map(str,s))

Python, 7911 (7704 + 207)

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=6*g/10
 print' '.join(map(str,s))

Python, 7910 (7704 + 206)

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

Source Link

created Dec 4, 2012 at 23:11

han

1.2k
8
10

Python, 7911 (7704 + 207)

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=6*g/10
 print' '.join(map(str,s))