Прикреплённый файл «2012-11-23.sort2.rnd.py»
Загрузка 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
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2012-12-14 12:14:10, 1.7 KB) [[attachment:2012-11-23.sort2.rnd.py]]
- [получить | показать] (2012-12-14 12:02:46, 1.1 KB) [[attachment:2012-11-30.fib.py]]
Вам нельзя прикреплять файлы к этой странице.