#!/usr/bin/python
#Copyleft (C) 1996 William Totten
#biell@udel.edu

#This library implements the shell sort method of sorting lists
#h is choosen using my sequence by default. While there is
#  no consensus as to which sequence is the best, mine seems to be
#  good.  More importantly mine is easy to generate.
#If you wish to try another sequence, just replace the call to
#  mine(N) on the 4th line of shellsort(), to the method of your choice.

def shellsort(list):
	N=len(list)

	for h in mine(N):
		for i in xrange(h,N):
			tmp=list[i]
			j=i
			while(j>=h and tmp<list[j-h]):
				list[j]=list[j-h]
				j=j-h
			list[j]=tmp

	return list


#Sequence Generators:

#The hibbard sequence is probably just slightly worse than the gonnet
#  sequence. If you wish to try this sequence, just replace the call to
#  gonnet(N) on the 4th line of shellsort(), to hibbard(N).
#  The sequence is as follows:
#    n > 2^k-1, 2^{k-1}-1, 2^{k-2}-1, ... , 1
def hibbard(n):
	list=[]
	elt=2
	while(n>=elt):
		list.insert(0,elt-1)
		elt=elt*2
	return list

#The Gonnet and Baeza-Yates sequence is (to my knowledge) considered
#  a rather good one.  The diminishing recurrence relation is:
#    h_0 = a*n
#    h_k = a*h_{k-1}; for h>=1 and a = .45454...
def gonnet(n):
	list=[]
	while(n>=5):
		n=(5*n-1)/11
		list.append(n)
	list.append(1)
	return list

#I have no information on who developed this sequence, but it is probably
#  the best one given here.  The sequence is defined by the relationship:
#    a_i = (9*4^i)-(9*2^i)+1
#    b_i = 4^i-(3*2^i)+1
#    h=merge(a, b)
def better(n):
	list=[1]
	four=1; two=1
	while(1):
		four=four*4
		two=two*2
		elt=4*four-6*two+1
		if(n<elt): break
		list.insert(0, elt)
		elt=9*four-9*two+1
		if(n<elt): break
		list.insert(0, elt)
	return list

#Mine is simple.  I have no proof of it's complexity, but it probably
#  is better than the hibbard and gonnet sequences.  The recurrence is:
#    h_0 = 1
#    h_k = (4*h_{k-1})+1
def mine(n):
	list=[]
	elt=1
	while(n>=elt):
		list.insert(0, elt)
		elt=(elt<<2)+1
	return list

#This sequence, not nessecarily developed by Knuth, was stated as being
#  a "... reasonable to choose the increments ...", on p.95 of
#  "The Art of Programming" Vol.3
#  The relation is as follows:
#    h_0 = 1
#    h_k = 3*h_{k-1}+1; for h_{k+1}<N
def knuth(n):
	list=[]
	elt=1
	next=(3*elt)+1
	while(next<n):
		list.insert(0, elt)
		elt=next
		next=(3*next)+1
	return list


if __name__ == '__main__':
	from posix import times
	from rlist import *
	list=[23,90,34,56,78,11,1,9,87,142,984,128,842,724,83,29,88,66,9]
	list=rlist(100000)
	t=times()[0]
	shellsort(list)
	print "User Time: ", times()[0] - t