Friendsnippets

1. Comb sort 11

   view plain - save this

   A Python implementation of the "Comb sort 11" algorithm. See http://en.wikipedia.org/wiki/Comb_sort

    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
   

   Posted by rmurri to python sort combsort algorithms ... saved by 1 person ... 0 comments ... 11 months, 1 week

2. SOrt a dict

   view plain - save this

   Quick tip to sort a dictionnary in python

    1 >>> a={'a':9,'b':8,'c':7}
    2 >>> a.keys().sort()
    3 >>> print a
    4 {'a': 9, 'c': 7, 'b': 8}
    5 >>> i =a.items()
    6 >>> i.sort()
    7 >>> print i
    8 [('a', 9), ('b', 8), ('c', 7)]
    9 >>> a={'a':9,'c':8,'b':7}
   10 >>> i =a.items()
   11 >>> i.sort()
   12 >>> print i
   13 [('a', 9), ('b', 7), ('c', 8)]
   14 >>> i.reverse()
   15 >>> print i
   16 [('c', 8), ('b', 7), ('a', 9)]
   17 >>> sorted(i)
   18 [('a', 9), ('b', 7), ('c', 8)]
   

   Posted by benoitc to python interactive console dict sort dictionnary reverse ... saved by 1 person ... 2 comments ... 1 year, 2 months

Pages : 1