Repository: keon/algorithms
Pull request #327 (2018-06-07 02:14:21)

Added simulation in bubble sort
I added simulation feature in bubble sort by adding  a new parameter 'simulation'. For example, if the input array is [4,2,3,4,6,1] and you set simulation = True when calling the function, you will see:
[4,2,3,4,6,1]
[2,4,3,4,6,1]
[2,3,4,4,6,1]
[2,3,4,1,4,6]
[2,3,1,4,4,6]
[2,1,3,4,4,6]
[1,2,3,4,4,6]

coveralls: ## Pull Request Test Coverage Report for [Build 528](https://coveralls.io/builds/17362652)

* **3** of **5**   **(60.0%)**  changed or added relevant lines in **1** file are covered.
* **2** unchanged lines in **1** file lost coverage.
* Overall coverage decreased (**-0.1%**) to **89.815%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/sort/bubble_sort.py](https://coveralls.io/builds/17362652/source?filename=algorithms%2Fsort%2Fbubble_sort.py#L21) | 3 | 5 | 60.0%
<!-- | **Total:** | **3** | **5** | **60.0%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/sort/top_sort.py](https://coveralls.io/builds/17362652/source?filename=algorithms%2Fsort%2Ftop_sort.py#L41) | 2 | 90.38% |
<!-- | **Total:** | **2** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17362652/badge)](https://coveralls.io/builds/17362652) |
| :-- | --: |
| Change from base [Build 477](https://coveralls.io/builds/17347146): |  -0.1% |
| Covered Lines: | 3201 |
| Relevant Lines: | 3564 |

---
##### 💛  - [Coveralls](https://coveralls.io)

lg970325: Can anyone explain why this makes error? It goes very well in my environment...

Patch:
diff --git a/README.md b/README.md
index f31075f..69b550d 100644
--- a/README.md
+++ b/README.md
@@ -222,6 +222,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
 - [sort](algorithms/sort)
+    - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
     - [bubble_sort](algorithms/sort/bubble_sort.py)
     - [bucket_sort](algorithms/sort/bucket_sort.py)
diff --git a/README_CN.md b/README_CN.md
index 4e93822..260bed2 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -206,6 +206,7 @@ pip3 uninstall -y algorithms
     - [randomized_set：随机集合](algorithms/set/randomized_set.py)
     - [set_covering：集合覆盖](algorithms/set/set_covering.py)
 - [sort：排序](algorithms/sort)
+    - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
     - [bubble_sort：冒泡排序](algorithms/sort/bubble_sort.py)
     - [bucket_sort](algorithms/sort/bucket_sort.py)
diff --git a/README_GE.md b/README_GE.md
index 8bc1fd2..2ec4b7a 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -227,6 +227,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
 - [sort](algorithms/sort)
+    - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
     - [bubble_sort](algorithms/sort/bubble_sort.py)
     - [bucket_sort](algorithms/sort/bucket_sort.py)
diff --git a/README_JP.md b/README_JP.md
index 0e63b9c..6279557 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -221,6 +221,7 @@ if __name__ == "__main__":
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
 - [sort : ソート](algorithms/sort)
+    - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
     - [bubble_sort](algorithms/sort/bubble_sort.py)
     - [bucket_sort](algorithms/sort/bucket_sort.py)
diff --git a/README_KR.md b/README_KR.md
index fde2147..d46fa47 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -218,6 +218,7 @@ if __name__ == "__main__":
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
 - [sort : 정렬 알고리즘](algorithms/sort)
+    - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
     - [bubble_sort](algorithms/sort/bubble_sort.py)
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index a2c6d3c..a7dba9a 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -1,3 +1,4 @@
+from .bitonic_sort import *
 from .bogo_sort import *
 from .bubble_sort import *
 from .comb_sort import *
diff --git a/algorithms/sort/bitonic_sort.py b/algorithms/sort/bitonic_sort.py
new file mode 100644
index 0000000..f8cad90
--- /dev/null
+++ b/algorithms/sort/bitonic_sort.py
@@ -0,0 +1,43 @@
+def bitonic_sort(arr, reverse=False):
+    """
+    bitonic sort is sorting algorithm to use multiple process, but this code not containing parallel process
+    It can sort only array that sizes power of 2
+    It can sort array in both increasing order and decreasing order by giving argument true(increasing) and false(decreasing)
+    
+    Worst-case in parallel: O(log(n)^2)
+    Worst-case in non-parallel: O(nlog(n)^2)
+    
+    reference: https://en.wikipedia.org/wiki/Bitonic_sorter
+    """
+    def compare(arr, reverse):
+        n = len(arr)//2
+        for i in range(n):
+            if reverse != (arr[i] > arr[i+n]):
+                arr[i], arr[i+n] = arr[i+n], arr[i]
+        return arr
+
+    def bitonic_merge(arr, reverse):
+        n = len(arr)
+        
+        if n <= 1:
+            return arr
+        
+        arr = compare(arr, reverse)
+        left = bitonic_merge(arr[:n // 2], reverse)
+        right = bitonic_merge(arr[n // 2:], reverse)
+        return left + right
+    
+    #end of function(compare and bitionic_merge) definition
+    n = len(arr)
+    if n <= 1:
+        return arr
+    # checks if n is power of two
+    if not (n and (not(n & (n - 1))) ):
+        raise ValueError("the size of input should be power of two")
+    
+    left = bitonic_sort(arr[:n // 2], True)
+    right = bitonic_sort(arr[n // 2:], False)
+
+    arr = bitonic_merge(left + right, reverse)
+        
+    return arr
diff --git a/algorithms/sort/bubble_sort.py b/algorithms/sort/bubble_sort.py
index 0a8a470..63c6c4f 100644
--- a/algorithms/sort/bubble_sort.py
+++ b/algorithms/sort/bubble_sort.py
@@ -4,19 +4,29 @@ https://en.wikipedia.org/wiki/Bubble_sort
 
 Worst-case performance: O(N^2)
 
+If you call bubble_sort(arr,True), you can see the process of the sort
+Default is simulation = False
+
 """
 
 
-def bubble_sort(arr):
+def bubble_sort(arr, simulation=False):
     def swap(i, j):
         arr[i], arr[j] = arr[j], arr[i]
 
     n = len(arr)
     swapped = True
+    
+    if simulation:
+        print(arr)
+    
     while swapped:
         swapped = False
         for i in range(1, n):
             if arr[i - 1] > arr[i]:
                 swap(i - 1, i)
                 swapped = True
+                if simulation:
+                    print(arr)
+                    
     return arr


Test patch:
diff --git a/tests/test_sort.py b/tests/test_sort.py
index 020b9a3..7d8ea8a 100644
--- a/tests/test_sort.py
+++ b/tests/test_sort.py
@@ -1,4 +1,5 @@
 from algorithms.sort import (
+    bitonic_sort,
     bogo_sort,
     bubble_sort,
     comb_sort,
@@ -22,6 +23,14 @@ class TestSuite(unittest.TestCase):
     def test_bogo_sort(self):
         self.assertEqual([1, 5, 23],
                          bogo_sort([1, 23, 5]))
+    
+    def test_bitonic_sort(self):
+        self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
+                         bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232]))
+        self.assertEqual([1, 2, 3, 5, 23, 57, 65, 1232],
+                         bitonic_sort([1, 3, 2, 5, 65, 23, 57, 1232],False))
+        self.assertEqual([1232, 65, 57, 23, 5, 3, 2, 1],
+                         bitonic_sort([1, 2, 3, 5, 65, 23, 57, 1232],True))  
    
     def test_bubble_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],