Прикреплённый файл «2012-11-23.sort2.py»
Загрузка 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
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2012-11-30 15:24:38, 1.2 KB) [[attachment:2012-11-23.AtoB.py]]
- [получить | показать] (2012-11-30 15:24:07, 1.2 KB) [[attachment:2012-11-23.findnum.py]]
- [получить | показать] (2012-12-14 11:59:28, 2.2 KB) [[attachment:2012-11-23.slagaemye.py]]
- [получить | показать] (2012-11-30 15:24:53, 1.6 KB) [[attachment:2012-11-23.sort2.py]]
- [получить | показать] (2012-11-30 15:25:07, 1.7 KB) [[attachment:2012-11-23.sort2.rnd.py]]
Вам нельзя прикреплять файлы к этой странице.