Back to index

python3.2  3.2.2
Classes | Functions | Variables
sortvisu Namespace Reference

Classes

class  Array
class  ArrayItem
class  SortDemo

Functions

def show_right
 top, bot = HIRO
def hide_left_right_pivot
def hide_left
def hide_right
def show_pivot
def hide_pivot
def swap
def compare
def reset
def message
def countswap
def countcompare
def updatereport
def steps
def interpolate
def uniform
def distinct
def randomize
def insertionsort
def selectionsort
def bubblesort
def quicksort
def demosort
def main

Variables

int XGRID = 10
int YGRID = 10
int WIDTH = 6
 ncompares
 nswaps

Function Documentation

def sortvisu.bubblesort (   array)

Definition at line 405 of file sortvisu.py.

00405 
00406 def bubblesort(array):
00407     size = array.getsize()
00408     array.reset("Bubble sort")
00409     for i in range(size):
00410         for j in range(1, size):
00411             if array.compare(j-1, j) > 0:
00412                 array.swap(j-1, j)
00413     array.message("Sorted")

def sortvisu.compare (   self,
  i,
  j 
)

Definition at line 165 of file sortvisu.py.

00165 
00166     def compare(self, i, j):
00167         self.countcompare()
00168         item = self.items[i]
00169         other = self.items[j]
00170         return item.compareto(other)

def sortvisu.countcompare (   self)

Definition at line 185 of file sortvisu.py.

00185 
00186     def countcompare(self):
00187         self.ncompares = self.ncompares + 1
00188         self.updatereport()

def sortvisu.countswap (   self)

Definition at line 181 of file sortvisu.py.

00181 
00182     def countswap(self):
00183         self.nswaps = self.nswaps + 1
00184         self.updatereport()

def sortvisu.demosort (   array)

Definition at line 475 of file sortvisu.py.

00475 
00476 def demosort(array):
00477     while 1:
00478         for alg in [quicksort, insertionsort, selectionsort, bubblesort]:
00479             randomize(array)
00480             alg(array)
00481 
00482 
00483 # Sort demo class -- usable as a Grail applet

Here is the call graph for this function:

def sortvisu.distinct (   array)

Definition at line 367 of file sortvisu.py.

00367 
00368 def distinct(array):
00369     size = array.getsize()
00370     array.setdata(range(1, size+1))
00371     array.reset("Distinct data, size %d" % size)

def sortvisu.hide_left (   self)

Definition at line 144 of file sortvisu.py.

00144 
00145     def hide_left(self):
00146         self.canvas.coords(self.left, (0, 0, 0, 0))

Definition at line 139 of file sortvisu.py.

00139 
00140     def hide_left_right_pivot(self):
00141         self.hide_left()
00142         self.hide_right()
00143         self.hide_pivot()

def sortvisu.hide_pivot (   self)

Definition at line 154 of file sortvisu.py.

00154 
00155     def hide_pivot(self):
00156         self.canvas.coords(self.pivot, (0, 0, 0, 0))

def sortvisu.hide_right (   self)

Definition at line 147 of file sortvisu.py.

00147 
00148     def hide_right(self):
00149         self.canvas.coords(self.right, (0, 0, 0, 0))

def sortvisu.insertionsort (   array)

Definition at line 380 of file sortvisu.py.

00380 
00381 def insertionsort(array):
00382     size = array.getsize()
00383     array.reset("Insertion sort")
00384     for i in range(1, size):
00385         j = i-1
00386         while j >= 0:
00387             if array.compare(j, j+1) <= 0:
00388                 break
00389             array.swap(j, j+1)
00390             j = j-1
00391     array.message("Sorted")

def sortvisu.interpolate (   oldpts,
  newpts,
  n 
)

Definition at line 347 of file sortvisu.py.

00347 
00348 def interpolate(oldpts, newpts, n):
00349     if len(oldpts) != len(newpts):
00350         raise ValueError("can't interpolate arrays of different length")
00351     pts = [0]*len(oldpts)
00352     res = [tuple(oldpts)]
00353     for i in range(1, n):
00354         for k in range(len(pts)):
00355             pts[k] = oldpts[k] + (newpts[k] - oldpts[k])*i//n
00356         res.append(tuple(pts))
00357     res.append(tuple(newpts))
00358     return res
00359 
00360 
00361 # Various (un)sorting algorithms

Here is the caller graph for this function:

def sortvisu.main ( void  )

Definition at line 628 of file sortvisu.py.

00628 
00629 def main():
00630     root = Tk()
00631     demo = SortDemo(root)
00632     root.protocol('WM_DELETE_WINDOW', demo.c_quit)
00633     root.mainloop()

def sortvisu.message (   self,
  msg 
)

Definition at line 178 of file sortvisu.py.

00178 
00179     def message(self, msg):
00180         self.label.config(text=msg)

def sortvisu.quicksort (   array)

Definition at line 414 of file sortvisu.py.

00414 
00415 def quicksort(array):
00416     size = array.getsize()
00417     array.reset("Quicksort")
00418     try:
00419         stack = [(0, size)]
00420         while stack:
00421             first, last = stack[-1]
00422             del stack[-1]
00423             array.show_partition(first, last)
00424             if last-first < 5:
00425                 array.message("Insertion sort")
00426                 for i in range(first+1, last):
00427                     j = i-1
00428                     while j >= first:
00429                         if array.compare(j, j+1) <= 0:
00430                             break
00431                         array.swap(j, j+1)
00432                         j = j-1
00433                 continue
00434             array.message("Choosing pivot")
00435             j, i, k = first, (first+last) // 2, last-1
00436             if array.compare(k, i) < 0:
00437                 array.swap(k, i)
00438             if array.compare(k, j) < 0:
00439                 array.swap(k, j)
00440             if array.compare(j, i) < 0:
00441                 array.swap(j, i)
00442             pivot = j
00443             array.show_pivot(pivot)
00444             array.message("Pivot at left of partition")
00445             array.wait(1000)
00446             left = first
00447             right = last
00448             while 1:
00449                 array.message("Sweep right pointer")
00450                 right = right-1
00451                 array.show_right(right)
00452                 while right > first and array.compare(right, pivot) >= 0:
00453                     right = right-1
00454                     array.show_right(right)
00455                 array.message("Sweep left pointer")
00456                 left = left+1
00457                 array.show_left(left)
00458                 while left < last and array.compare(left, pivot) <= 0:
00459                     left = left+1
00460                     array.show_left(left)
00461                 if left > right:
00462                     array.message("End of partition")
00463                     break
00464                 array.message("Swap items")
00465                 array.swap(left, right)
00466             array.message("Swap pivot back")
00467             array.swap(pivot, right)
00468             n1 = right-first
00469             n2 = last-left
00470             if n1 > 1: stack.append((first, right))
00471             if n2 > 1: stack.append((left, last))
00472         array.message("Sorted")
00473     finally:
00474         array.hide_partition()

def sortvisu.randomize (   array)

Definition at line 372 of file sortvisu.py.

00372 
00373 def randomize(array):
00374     array.reset("Randomizing")
00375     n = array.getsize()
00376     for i in range(n):
00377         j = random.randint(0, n-1)
00378         array.swap(i, j)
00379     array.message("Randomized")

Here is the call graph for this function:

Here is the caller graph for this function:

def sortvisu.reset (   self,
  msg 
)

Definition at line 171 of file sortvisu.py.

00171 
00172     def reset(self, msg):
00173         self.ncompares = 0
00174         self.nswaps = 0
00175         self.message(msg)
00176         self.updatereport()
00177         self.hide_partition()

def sortvisu.selectionsort (   array)

Definition at line 392 of file sortvisu.py.

00392 
00393 def selectionsort(array):
00394     size = array.getsize()
00395     array.reset("Selection sort")
00396     try:
00397         for i in range(size):
00398             array.show_partition(i, size)
00399             for j in range(i+1, size):
00400                 if array.compare(i, j) > 0:
00401                     array.swap(i, j)
00402         array.message("Sorted")
00403     finally:
00404         array.hide_partition()

def sortvisu.show_pivot (   self,
  pivot 
)

Definition at line 150 of file sortvisu.py.

00150 
00151     def show_pivot(self, pivot):
00152         x1, y1, x2, y2 = self.items[pivot].position()
00153         self.canvas.coords(self.pivot, (0, y1 - 2, 9999, y1 - 2))

def sortvisu.show_right (   self,
  right 
)

top, bot = HIRO

Definition at line 131 of file sortvisu.py.

00131 
00132     def show_right(self, right):
00133         if not 0 <= right < self.size:
00134             self.hide_right()
00135             return
00136         x1, y1, x2, y2 = self.items[right].position()
00137         self.canvas.coords(self.right, (x2 + 2, 0, x2 + 2, 9999))
00138         self.master.update()

def sortvisu.steps (   here,
  there 
)

Definition at line 337 of file sortvisu.py.

00337 
00338 def steps(here, there):
00339     nsteps = abs(here - there)
00340     if nsteps <= 3:
00341         nsteps = nsteps * 3
00342     elif nsteps <= 5:
00343         nsteps = nsteps * 2
00344     elif nsteps > 10:
00345         nsteps = 10
00346     return nsteps

Here is the caller graph for this function:

def sortvisu.swap (   self,
  i,
  j 
)

Definition at line 157 of file sortvisu.py.

00157 
00158     def swap(self, i, j):
00159         if i == j: return
00160         self.countswap()
00161         item = self.items[i]
00162         other = self.items[j]
00163         self.items[i], self.items[j] = other, item
00164         item.swapwith(other)

Here is the caller graph for this function:

def sortvisu.uniform (   array)

Definition at line 362 of file sortvisu.py.

00362 
00363 def uniform(array):
00364     size = array.getsize()
00365     array.setdata([(size+1)//2] * size)
00366     array.reset("Uniform data, size %d" % size)

def sortvisu.updatereport (   self)

Definition at line 189 of file sortvisu.py.

00189 
00190     def updatereport(self):
00191         text = "%d cmps, %d swaps" % (self.ncompares, self.nswaps)
00192         self.report.config(text=text)
00193 


Variable Documentation

Definition at line 172 of file sortvisu.py.

Definition at line 173 of file sortvisu.py.

Definition at line 26 of file sortvisu.py.

Definition at line 24 of file sortvisu.py.

Definition at line 25 of file sortvisu.py.