-
Notifications
You must be signed in to change notification settings - Fork 0
/
BitonicSort.py
46 lines (40 loc) · 1.54 KB
/
BitonicSort.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
'''
Bitonic Sort ; Size of input should be of the form 2^p
Time Complexity: O(log^2(N)) ; log^2(N) = log(log(N))
Space Complexity: O(N * log^2(N))
'''
import sys
from algorithms.Algorithm import Algorithm
class BitonicSort(Algorithm):
def __init__(self):
super().__init__("Bitonic Sort")
def algorithm(self, low = 0, count = None, ASC = True):
if not self.checkIsPowerOfTwo():
sys.exit("Error: Size of input array is not of the form 2^p")
if count == None:
count = len(self.array)
if count > 1:
self.algorithm(low, count//2, True)
self.algorithm(low + count//2, count//2, False)
self.BitonicMerge(low, count, ASC)
def BitonicMerge(self, low, count, ASC):
if count > 1:
self.BitonicCompare(low, count, ASC)
self.BitonicMerge(low, count//2, ASC)
self.BitonicMerge(low + count//2, count//2, ASC)
def BitonicCompare(self, low, count, ASC):
m = count//2
for i in range(low, low+m):
if (self.array[i] > self.array[m+i]) is ASC:
self.array[i], self.array[m+i] = self.array[m+i], self.array[i]
#visualise the sorting
self.update(i, m+i)
def checkIsPowerOfTwo(self):
n = len(self.array)
if n == 0:
return False
while n != 1:
if n % 2 != 0:
return False
n //= 2
return True