-
Notifications
You must be signed in to change notification settings - Fork 0
/
3.py
58 lines (45 loc) · 2.89 KB
/
3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
'''
LSD-сортировка с младших разрядов.
MSD-сортировка со старших разрядов.
Сложность LSD-сортировки:
m - кол-во разрядов, n - кол-во объектов. Цифровая сортировка выполняет k итераций,
на каждой из которой выполняется устойчивая сортировка и не более O(1) других операций. T(n) - время работы устойчивой сортировки.
Следовательно время работы цифровой сортировки O(m*T(n))
Сложность MSD-сортировки:
Пусть значения разрядов меньше b, а количество разрядов — k .При сортировке массива из одинаковых элементов MSD-сортировкой
на каждом шаге все элементы будут находится в неубывающей по размеру корзине,
а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной O(n*k).
*Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на b частей. Как только размер корзины станет равен 1,
сортировка перестанет рекурсивно запускаться в этой корзине.
Таким образом, асимптотика будет Ω(n*logb(n)). Это хорошо тем, что не зависит от числа разрядов.
**Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана,
и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).
'''
f=open('radixsort.in', 'r')
a=(f.readline().split())
n,length,k=int(a[0]),int(a[1]),int(a[2])
A=[]
for i in range(n):
s=str(*(f.readline().split()))
A.append(s)
for i in range(length-1,-1,-1):
B=dict()
for t in range(97,123):
B[chr(t)]=[]
for x in A:
figure = x[i]
if figure in B:
B[figure].append(x)
else:
B[figure]=[x]
A=[]
for ki in B:
for kj in B[ki]:
A.append(kj)
k-=1
if k==0:
break
t=open('radixsort.out','w')
for z in A:
print(z , file =t)
t.close()