прикреплённый файл:2012-11-23.sort2.rnd.py к странице LecturesVMSH/Python/2012-11-30

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Изобрести более эффективный алгоритм сортировки списка (не массива!), основанный на бинарном поиске
   5 Оформить два алгоритма сортировки (медленный и быстрый) в виде функций. Сравнить время выполнения
   6 
   7 Тестирующая программа
   8 '''
   9 
  10 def bubblesort(L):
  11     '''Сортировка пузырьком'''
  12     for i in xrange(len(L)-1):          # N-1 оборотов цикла
  13         for j in xrange(len(L)-i-1):    # N-i-1 ооротов цикла
  14             if L[j]>L[j+1]:
  15                 L[j],L[j+1] = L[j+1],L[j]
  16 # Итого (N-2)+(N-3)+...+2+1 = (N-1)*(N-2)/2 = N**2/2 - 3*N/2 + 1
  17 
  18 def inssort(L):
  19     '''Сортировка вставками'''
  20     for w in xrange(1,len(L)):          # N-1 оборотов цикла
  21         b,e=0,w
  22         while b<e:                      # e-b каждый оборот уменьшается вдвое
  23             m=(b+e)/2                   
  24             if L[m]==L[w]:              # => не боле, чем log по основанию 2 от w
  25                 break                   # оборотов цикла
  26             elif L[m]>L[w]:
  27                 e=e-(e-b+1)/2
  28             else:
  29                 b=b+(e-b+1)/2
  30         else:
  31             m=b
  32         L.insert(m,L.pop(w))
  33 # Итого < (N-1)*log(2,N-1)
  34 
  35 import random
  36 W=10000
  37 l=random.sample(xrange(W),W/10)*10
  38 random.shuffle(l)
  39 # Имена функуций -- тоже объекты!
  40 for fun in (bubblesort, inssort):
  41     L=l[:]
  42     print "Start"
  43     fun(L)
  44     print fun