прикреплённый файл:sort.py к странице LecturesVMSH/2011-02-09

   1 #!/usr/bin/python
   2 # coding: utf8
   3 '''
   4 Различные алгоритмы сортировки, их оценка и отображение
   5 '''
   6 
   7 import sort_show, sort_count, sys, random
   8 
   9 def sCompare(p):
  10     for i in xrange(0,len(p)-1):
  11         m=i
  12         for j in xrange(i+1,len(p)):
  13             if sort_show.GT(p,j,m):
  14                 m=j
  15         sort_show.Swap(p,i,m)
  16 
  17 def sQuick(p):
  18     parts=[(0,len(p))]  # отрезки, которые надо поделить на большие и малые значения
  19     while parts:
  20         nparts=[]
  21         for beg,end in parts:
  22             if beg>end-2: continue
  23             if beg==end-2:
  24                 if sort_show.GT(p,end-1,beg):
  25                     sort_show.Swap(p,end-1,beg)
  26                 continue
  27             i,j,m=beg,end-1,end-1
  28             while i<j:
  29                 while sort_show.GT(p,i,m):
  30                     i+=1
  31                 sort_show.Swap(p,i,j)
  32                 m=i
  33                 while sort_show.GT(p,m,j):
  34                     j-=1
  35                 sort_show.Swap(p,i,j)
  36                 m=j
  37             nparts+=[(beg,i),(j,end)]
  38         parts=nparts
  39 
  40 def sMerge(p):
  41     i,parts=0,[]
  42     while i<len(p)-1: # первоначальное разбиение
  43         if sort_show.GT(p,i+1,i):
  44             sort_show.Swap(p,i,i+1)
  45         j=i+1
  46         while j<len(p)-1 and not sort_show.GT(p,j+1,j):
  47             j+=1
  48         parts.append((i,j+1))
  49         i=j+1
  50     if i==len(p)-1: parts.append((i,i+1))
  51     while len(parts)>1:
  52         parts,oparts=[],parts
  53         while len(oparts)>1:
  54             p1,p2=oparts.pop(0),oparts.pop(0)
  55             s1,s2=range(*p1),range(*p2)
  56             ind=[]
  57             while s1+s2:
  58                 s=s1 and (not s2 or sort_show.GT(p,s1[0],s2[0])) and s1 or s2
  59                 ind.append(s.pop(0))
  60             sort_show.Swapn(p,ind,range(p1[0],p2[1]))
  61             parts.append((p1[0],p2[1]))
  62         if oparts: parts.append(oparts.pop())
  63 
  64 N=len(sys.argv)>1 and int(sys.argv[1]) or 32
  65 F=len(sys.argv)>2 and eval("s"+sys.argv[2]) or sCompare
  66 P=len(sys.argv)>3 and float(sys.argv[3]) or 0.1
  67 
  68 sort_show.Init((1024,768),P)
  69 
  70 A=random.sample(xrange(N),N)
  71 F(A)
  72 sort_show.Fill(A)
  73 sort_show.Wait()
  74 print sort_count.COUNT