Attachment '2012-11-23.sort2.rnd.py'
Download 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
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.- [get | view] (2012-11-30 12:24:38, 1.2 KB) [[attachment:2012-11-23.AtoB.py]]
- [get | view] (2012-11-30 12:24:07, 1.2 KB) [[attachment:2012-11-23.findnum.py]]
- [get | view] (2012-12-14 08:59:28, 2.2 KB) [[attachment:2012-11-23.slagaemye.py]]
- [get | view] (2012-11-30 12:24:53, 1.6 KB) [[attachment:2012-11-23.sort2.py]]
- [get | view] (2012-11-30 12:25:07, 1.7 KB) [[attachment:2012-11-23.sort2.rnd.py]]
You are not allowed to attach a file to this page.