Skip to content

Commit 69d4b7d

Browse files
hsi1032keon
hsi1032
authored and
keon
committed
Create bitonic_sort.py in /algorithms/sort/ and update test_sort, __init__ and all README files (keon#317)
* Create bitonic_sort.py * Update __init__.py * Update test_sort.py * Update README.md * Update README_CN.md * Update README_GE.md * Update README_JP.md * Update README_KR.md * Update bitonic_sort.py * Update bitonic_sort.py * Update bitonic_sort.py * Update test_sort.py * Update test_sort.py * Update bitonic_sort.py * Update bitonic_sort.py * Update bitonic_sort.py * Update bitonic_sort.py * Update bitonic_sort.py
1 parent de286fd commit 69d4b7d

File tree

8 files changed

+58
-0
lines changed

8 files changed

+58
-0
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -222,6 +222,7 @@ If you want to uninstall algorithms, it is as simple as:
222222
- [randomized_set](algorithms/set/randomized_set.py)
223223
- [set_covering](algorithms/set/set_covering.py)
224224
- [sort](algorithms/sort)
225+
- [bitonic_sort](algorithms/sort/bitonic_sort.py)
225226
- [bogo_sort](algorithms/sort/bogo_sort.py)
226227
- [bubble_sort](algorithms/sort/bubble_sort.py)
227228
- [bucket_sort](algorithms/sort/bucket_sort.py)

‎README_CN.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -206,6 +206,7 @@ pip3 uninstall -y algorithms
206206
- [randomized_set：随机集合](algorithms/set/randomized_set.py)
207207
- [set_covering：集合覆盖](algorithms/set/set_covering.py)
208208
- [sort：排序](algorithms/sort)
209+
- [bitonic_sort](algorithms/sort/bitonic_sort.py)
209210
- [bogo_sort](algorithms/sort/bogo_sort.py)
210211
- [bubble_sort：冒泡排序](algorithms/sort/bubble_sort.py)
211212
- [bucket_sort](algorithms/sort/bucket_sort.py)

‎README_GE.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
227227
- [randomized_set](algorithms/set/randomized_set.py)
228228
- [set_covering](algorithms/set/set_covering.py)
229229
- [sort](algorithms/sort)
230+
- [bitonic_sort](algorithms/sort/bitonic_sort.py)
230231
- [bogo_sort](algorithms/sort/bogo_sort.py)
231232
- [bubble_sort](algorithms/sort/bubble_sort.py)
232233
- [bucket_sort](algorithms/sort/bucket_sort.py)

‎README_JP.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -221,6 +221,7 @@ if __name__ == "__main__":
221221
- [randomized_set](algorithms/set/randomized_set.py)
222222
- [set_covering](algorithms/set/set_covering.py)
223223
- [sort : ソート](algorithms/sort)
224+
- [bitonic_sort](algorithms/sort/bitonic_sort.py)
224225
- [bogo_sort](algorithms/sort/bogo_sort.py)
225226
- [bubble_sort](algorithms/sort/bubble_sort.py)
226227
- [bucket_sort](algorithms/sort/bucket_sort.py)

‎README_KR.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,6 +218,7 @@ if __name__ == "__main__":
218218
- [randomized_set](algorithms/set/randomized_set.py)
219219
- [set_covering](algorithms/set/set_covering.py)
220220
- [sort : 정렬 알고리즘](algorithms/sort)
221+
- [bitonic_sort](algorithms/sort/bitonic_sort.py)
221222
- [bogo_sort](algorithms/sort/bogo_sort.py)
222223
- [bubble_sort](algorithms/sort/bubble_sort.py)
223224
- [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)

‎algorithms/sort/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
from .bitonic_sort import *
12
from .bogo_sort import *
23
from .bubble_sort import *
34
from .comb_sort import *

‎algorithms/sort/bitonic_sort.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
def bitonic_sort(arr, reverse=False):
2+
"""
3+
bitonic sort is sorting algorithm to use multiple process, but this code not containing parallel process
4+
It can sort only array that sizes power of 2
5+
It can sort array in both increasing order and decreasing order by giving argument true(increasing) and false(decreasing)
6+
7+
Worst-case in parallel: O(log(n)^2)
8+
Worst-case in non-parallel: O(nlog(n)^2)
9+
10+
reference: https://en.wikipedia.org/wiki/Bitonic_sorter
11+
"""
12+
def compare(arr, reverse):
13+
n = len(arr)//2
14+
for i in range(n):
15+
if reverse != (arr[i] > arr[i+n]):
16+
arr[i], arr[i+n] = arr[i+n], arr[i]
17+
return arr
18+
19+
def bitonic_merge(arr, reverse):
20+
n = len(arr)
21+
22+
if n <= 1:
23+
return arr
24+
25+
arr = compare(arr, reverse)
26+
left = bitonic_merge(arr[:n // 2], reverse)
27+
right = bitonic_merge(arr[n // 2:], reverse)
28+
return left + right
29+
30+
#end of function(compare and bitionic_merge) definition
31+
n = len(arr)
32+
if n <= 1:
33+
return arr
34+
# checks if n is power of two
35+
if not (n and (not(n & (n - 1))) ):
36+
raise ValueError("the size of input should be power of two")
37+
38+
left = bitonic_sort(arr[:n // 2], True)
39+
right = bitonic_sort(arr[n // 2:], False)
40+
41+
arr = bitonic_merge(left + right, reverse)
42+
43+
return arr

‎tests/test_sort.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
from algorithms.sort import (
2+
bitonic_sort,
23
bogo_sort,
34
bubble_sort,
45
comb_sort,
@@ -22,6 +23,14 @@ class TestSuite(unittest.TestCase):
2223
def test_bogo_sort(self):
2324
self.assertEqual([1, 5, 23],
2425
bogo_sort([1, 23, 5]))
26+
27+
def test_bitonic_sort(self):
28+
self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
29+
bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232]))
30+
self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
31+
bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232],False))
32+
self.assertEqual([1232, 65, 57, 23, 5, 3, 2, 1],
33+
bitonic_sort([1, 2, 3, 5, 65, 23, 57, 1232],True))
2534

2635
def test_bubble_sort(self):
2736
self.assertEqual([1, 5, 23, 57, 65, 1232],

0 commit comments

Comments
 (0)