algorithms_python/sort_complexity.py at master · beling/algorithms_python · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

importmatplotlib.pyplotasplt
fromrandomimportrandrange
fromcopyimportcopy

defmin_index(tab, start=0):
globalit
res=start
foriinrange(start+1, len(tab)):
it+=1
iftab[i] <tab[res]:
res=i
returnres

defsort_by_min(tab):
forstartinrange(len(tab)):
m=min_index(tab, start)
tab[start], tab[m] =tab[m], tab[start]

defmerge(A, B):
globalit
res= []
a=0
b=0
whilea<len(A) andb<len(B):
it+=1
ifA[a] <=B[b]:
res.append(A[a])
a+=1
else:
res.append(B[b])
b+=1
foriinrange(a, len(A)):
res.append(A[i])
foriinrange(b, len(B)):
res.append(B[i])
returnres

defmerge_sort(tab):
iflen(tab) <=1: returntab
mid=len(tab) //2
returnmerge(
merge_sort(tab[:mid]),
merge_sort(tab[mid:])
 )

defcount_sort(tab):
globalit
count= [0] *1001
forvintab:
it+=1
count[v] +=1
res= []
forvinrange(1001):
for_inrange(count[v]):
res.append(v)
returnres

defbinary_search(T, e):
start=0
end=len(T)
whilestart<end:
mid=start+ (end-start) //2
ifT[mid] ==e: returnmid
ifT[mid] >e:
end=mid
else:
start=mid+1
return-1

X= []
Y= []
Ymerge= []
Ycount= []
tab= []
fortab_sizeinrange(1, 100):
tab.append(randrange(0, 1001))
X.append(len(tab))
it=0
sort_by_min(copy(tab))
Y.append(it)
it=0
merge_sort(tab)
Ymerge.append(it)
it=0
count_sort(tab)
Ycount.append(it)

plt.plot(X, Y, label='sort by swapping with minimum')
plt.plot(X, Ymerge, label='merge sort')
plt.plot(X, Ycount, label='count sort')
plt.legend(loc="upper left")
plt.show()