シェルソート

shell_sort.py

def shell_sort(a):
  size = len(a)
  h = 1 
  while True:
    h = 3 * h + 1
    if h > size: break
  while True:
    h /= 3
    #print "h=%d" % h
    for i in range(h, size):
      v = a[i]
      j = i
      while j >= h and v < a[j - h]:
        a[j] = a[j - h]
        j -= h
      if i != j: a[j] = v
    #print "a=%s" % a
    if h == 1: break

  

test_shell_sort.py

#!/usr/bin/env python2.7
from test import test_support
import unittest
import random
from shell_sort import *
class TestClass(unittest.TestCase):
  def test_sort(self):
    for i in range(10000):
      origine = range(random.randint(2, 100))
      a = origine[:]
      while a == origine: random.shuffle(a)
      self.assertNotEquals(origine, a)
      shell_sort(a)
      self.assertEquals(origine, a)
test_support.run_unittest(TestClass)