PythonLabs/lab-4.py at master · temurti/PythonLabs · 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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import random
import time


def CountSort(a, k):
	c = [0 for i in xrange(k)]
	b = [0 for i in a]
	for i in a:
		c[i] += 1
	for i in xrange(1, k):
		c[i] += c[i-1]
	for i in a:
		c[i] -= 1
		b[c[i]] = i
	return b


def CountSort2(a, d):
	k = 10
	c = [0 for i in xrange(k)]
	b = [0 for i in a]
	for i in a:
		c[int(i[d])] += 1
	for i in xrange(1, k):
		c[i] += c[i-1]
	for i in reversed(a):
		c[int(i[d])] -= 1
		b[c[int(i[d])]] = i
	return b


def RadixSort(a, d):
	a = map(lambda x: str(x).zfill(d), a)
	for i in xrange(d-1, -1, -1):
		a = CountSort2(a, i)
	return map(int, a)


def BucketSortSimple(a):
	bucket1,bucket2,bucket3 = [],[],[]
	for i in xrange(len(a)):
		if a[i] in range(31):
			bucket1.append(a[i])
		elif a[i] in range(61):
			bucket2.append(a[i])
		elif a[i] in range(101):
			bucket3.append(a[i])
		elif a[i] in range(141):
			bucket3.append(a[i])

	SelectSort(bucket1)
	SelectSort(bucket2)
	SelectSort(bucket3)
	final = bucket1 + bucket2 + bucket3
	return final


class Node:
	def __init__(self,value=None, next=None, prev=None):
		self.value = value
		self.next = next
		self.prev = prev

def insertSortList(head):
	i = head.next
	while i.next:
		j = i.next
		while j.prev != head and j.value < j.prev.value:
			j.value, j.prev.value = j.prev.value, j.value
			j = j.prev
		i = i.next


def bucketSort(a, k):
	n = len(a)
	m = max(a)
	b = [Node() for i in xrange(k)]
	for i in a:
		index = int((k-1)*(float(i)/m))
		x = b[index]
		while x.next:	x = x.next
		x.next = Node(i)
		x.next.prev = x
	for i in b:
		if i.next: insertSortList(i)
	tmp = 0
	for i in b:
		x = i.next
		while x:
			a[tmp] = x.value
			tmp += 1
			x = x.next
	return a


q = 10**4
a = range(q)
random.shuffle(a)


t = time.clock()
CountSort(a[:],q)
print  "CountSort :" , time.clock() - t  ,"sec\n"

t = time.clock()
RadixSort(a[:],4)
print  "RadixSort :" , time.clock() - t  ,"sec\n"

t = time.clock()
bucketSort(a[:],q)
print  "BucketSort :" , time.clock() - t  ,"sec\n"