Attachment '2012-11-23.sort2.py'

Download

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

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.