Package nltk_lite :: Package misc :: Module sort
[hide private]
[frames] | no frames]

Source Code for Module nltk_lite.misc.sort

  1  # Natural Language Toolkit: List Sorting 
  2  # 
  3  # Copyright (C) 2001-2007 University of Pennsylvania 
  4  # Author: Steven Bird <sb@csse.unimelb.edu.au> 
  5  # URL: <http://nltk.sf.net> 
  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 a, count_a = _merge_lists(b, c) 99 count = count_a + count_b + count_c 100 return count
101 102 ################################################################## 103 # Quick Sort 104 ################################################################## 105
106 -def _partition(a, l, r):
107 p = a[l]; i = l; j = r+1 108 count = 0 109 while True: 110 while i < r: 111 i += 1 112 if a[i] >= p: break 113 while j > l: 114 j -= 1 115 if j < l or a[j] <= p: break 116 a[i],a[j] = a[j],a[i] # swap 117 count += 1 118 if i >= j: break 119 a[i],a[j] = a[j],a[i] # undo last swap 120 a[l],a[j] = a[j],a[l] 121 return j, count
122
123 -def _quick(a, l, r):
124 count = 0 125 if l<r: 126 s, count = _partition(a, l, r) 127 count += _quick(a, l, s-1) 128 count += _quick(a, s+1, r) 129 return count
130
131 -def quick(a):
132 return _quick(a, 0, len(a)-1)
133 134 ################################################################## 135 # Demonstration 136 ################################################################## 137
138 -def demo():
139 from random import shuffle 140 141 for size in (10, 20, 50, 100, 200, 500, 1000): 142 a = range(size) 143 144 # various sort methods 145 shuffle(a); count_selection = selection(a) 146 shuffle(a); count_bubble = bubble(a) 147 shuffle(a); count_merge = merge(a) 148 shuffle(a); count_quick = quick(a) 149 150 print "size=%5d: selection=%8d, bubble=%8d, merge=%6d, quick=%6d" %\ 151 (size, count_selection, count_bubble, count_merge, count_quick)
152 153 if __name__ == '__main__': 154 demo() 155