Friendsnippets

 1 def combsort11(seq, cmp=None, key=None):
 2     """Sort `seq` *in-place* with the CombSort11 algorithm.
 3     Optional arguments `cmp` and `key` have same meaning as in the
 4     Python `sorted` built-in function.
 5 
 6     Examples::
 7     
 8       >>> seq = [8,4,5,0,2,3,1,6,7]
 9       >>> combsort11(seq)
10       >>> seq
11       [0, 1, 2, 3, 4, 5, 6, 7, 8]
12 
13       >>> seq = range(9)
14       >>> combsort11(seq, cmp=-cmp)
15       >>> seq
16       [8, 7, 6, 5, 4, 3, 2, 1, 0]
17       
18       >>> seq = [(1,0), (2,3), (1,3), (1,-1)]
19       >>> combsort11(seq, key=lambda x: 10*x[0] + x[1])
20       >>> seq
21       [(1, -1), (1, 0), (1, 3), (2, 3)]
22 
23     See http://en.wikipedia.org/wiki/Comb_sort for an explanation and
24     the original pseudocode.
25     """
26     
27     if cmp is None:
28         cmp = __builtins__.cmp
29     if key is None:
30         key = lambda x: x
31         
32     gap = len(seq)  # initialize gap size
33     swap_occurred = False
34     while (gap > 1) or swap_occurred:
35         # update the gap value for a next comb
36         if gap > 1:
37             gap = int(gap / 1.247330950103979)
38             # adjust gap size for final steps of the sequence;
39             # see http://en.wikipedia.org/wiki/Comb_sort#Combsort11
40             if gap in (9, 10):
41                 gap = 11
42         
43         # a single "comb" over the input list
44         swap_occurred = False 
45         for i in xrange(len(seq) - gap):
46             j = i + gap
47             if cmp(key(seq[i]), key(seq[j])) > 0:
48                 # swap seq[i] and seq[i+gap]
49                 seq[i], seq[j] = seq[j], seq[i]
50                 swap_occurred = True