Source Code for Module nltk.misc.sort

  1  # Natural Language Toolkit: List Sorting 
  2  # 
  3  # Copyright (C) 2001-2008 NLTK Project 
  4  # Author: Steven Bird <[email protected]> 
  5  # URL: <http://nltk.org> 
  6  # For license information, see LICENSE.TXT 
  7   
  8  """ 
  9  This module provides a variety of list sorting algorithms, to 
 10  illustrate the many different algorithms (recipes) for solving a 
 11  problem, and how to analyze algorithms experimentally. 
 12  """ 
 13   
 14  # These algorithms are taken from: 
 15  # Levitin (2004) The Design and Analysis of Algorithms 
 16   
 17   
 18  ################################################################## 
 19  # Selection Sort 
 20  ################################################################## 
 21   
 22 -def selection(a): 
 23      """ 
 24      Selection Sort: scan the list to find its smallest element, then 
 25      swap it with the first element.  The remainder of the list is one 
 26      element smaller; apply the same method to this list, and so on. 
 27      """ 
 28      count = 0 
 29   
 30      for i in range(len(a) - 1): 
 31          min = i 
 32   
 33          for j in range(i+1, len(a)): 
 34              if a[j] < a[min]: 
 35                  min = j 
 36   
 37              count += 1 
 38   
 39          a[min],a[i] = a[i],a[min] 
 40   
 41      return count 
 42   
 43  ################################################################## 
 44  # Bubble Sort 
 45  ################################################################## 
 46   
 47 -def bubble(a): 
 48      """ 
 49      Bubble Sort: compare adjacent elements of the list left-to-right, 
 50      and swap them if they are out of order.  After one pass through 
 51      the list swapping adjacent items, the largest item will be in 
 52      the rightmost position.  The remainder is one element smaller; 
 53      apply the same method to this list, and so on. 
 54      """ 
 55      count = 0 
 56      for i in range(len(a)-1): 
 57          for j in range(len(a)-i-1): 
 58              if a[j+1] < a[j]: 
 59                  a[j],a[j+1] = a[j+1],a[j] 
 60                  count += 1 
 61      return count 
 62   
 63   
 64  ################################################################## 
 65  # Merge Sort 
 66  ################################################################## 
 67   
 68 -def _merge_lists(b, c): 
 69      count = 0 
 70      i = j = 0 
 71      a = [] 
 72      while (i < len(b) and j < len(c)): 
 73          count += 1 
 74          if b[i] <= c[j]: 
 75              a.append(b[i]) 
 76              i += 1 
 77          else: 
 78              a.append(c[j]) 
 79              j += 1 
 80      if i == len(b): 
 81          a += c[j:] 
 82      else: 
 83          a += b[i:] 
 84      return a, count 
 85       
 86 -def merge(a): 
 87      """ 
 88      Merge Sort: split the list in half, and sort each half, then 
 89      combine the sorted halves. 
 90      """ 
 91      count = 0 
 92      if len(a) > 1: 
 93          midpoint = len(a)/2 
 94          b = a[:midpoint] 
 95          c = a[midpoint:] 
 96          count_b = merge(b) 
 97          count_c = merge(c) 
 98          result, count_a = _merge_lists(b, c) 
 99          a[:] = result # copy the result back into a. 
100          count = count_a + count_b + count_c 
101      return count 
102   
103  ################################################################## 
104  # Quick Sort 
105  ################################################################## 
106   
107 -def _partition(a, l, r): 
108      p = a[l]; i = l; j = r+1 
109      count = 0 
110      while True: 
111          while i < r: 
112              i += 1 
113              if a[i] >= p: break 
114          while j > l: 
115              j -= 1 
116              if j < l or a[j] <= p: break 
117          a[i],a[j] = a[j],a[i]               # swap 
118          count += 1 
119          if i >= j: break 
120      a[i],a[j] = a[j],a[i]                   # undo last swap 
121      a[l],a[j] = a[j],a[l] 
122      return j, count 
123   
124 -def _quick(a, l, r): 
125      count = 0 
126      if l<r: 
127          s, count = _partition(a, l, r) 
128          count += _quick(a, l, s-1) 
129          count += _quick(a, s+1, r) 
130      return count 
131   
132 -def quick(a): 
133      return _quick(a, 0, len(a)-1) 
134   
135  ################################################################## 
136  # Demonstration 
137  ################################################################## 
138   
139 -def demo(): 
140      from random import shuffle 
141   
142      for size in (10, 20, 50, 100, 200, 500, 1000): 
143          a = range(size) 
144   
145          # various sort methods 
146          shuffle(a); count_selection = selection(a) 
147          shuffle(a); count_bubble    = bubble(a) 
148          shuffle(a); count_merge     = merge(a) 
149          shuffle(a); count_quick     = quick(a) 
150   
151          print (("size=%5d:  selection=%8d,  bubble=%8d,  " 
152                  "merge=%6d,  quick=%6d") % 
153                 (size, count_selection, count_bubble, 
154                  count_merge, count_quick)) 
155   
156  if __name__ == '__main__': 
157      demo() 
158