Repository: keon/algorithms
Pull request #296 (2018-06-01 14:37:30)

Created bucket_sort.py & shell_sort.py and Updated test_sort.py
It seems like there are no bucket sort and shell sort in the sort file, so I added them. Updated test_sort.py as well - added bucket and shell sort in the test.

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

* **38** of **38**   **(100.0%)**  changed or added relevant lines in **3** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.1%**) to **91.422%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/17272720/badge)](https://coveralls.io/builds/17272720) |
| :-- | --: |
| Change from base [Build 304](https://coveralls.io/builds/17266764): |  0.1% |
| Covered Lines: | 2707 |
| Relevant Lines: | 2961 |

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


Patch:
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index 20a3cf3..665a0d7 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -6,3 +6,5 @@ from .insertion_sort import *
 from .merge_sort import *
 from .quick_sort import *
 from .selection_sort import *
+from .bucket_sort import *
+from .shell_sort import *
diff --git a/algorithms/sort/bucket_sort.py b/algorithms/sort/bucket_sort.py
new file mode 100644
index 0000000..d89232c
--- /dev/null
+++ b/algorithms/sort/bucket_sort.py
@@ -0,0 +1,28 @@
+def bucket_sort(arr):
+    ''' Bucket Sort
+        Complexity: O(n^2)
+        The complexity is dominated by nextSort
+    '''
+    # The number of buckets and make buckets
+    num_buckets = len(arr)
+    buckets = [[] for bucket in range(num_buckets)]
+    # Assign values into bucket_sort
+    for value in arr:
+        index = value * num_buckets // (max(arr) + 1)
+        buckets[index].append(value)
+    # Sort
+    sorted_list = []
+    for i in range(num_buckets):
+        sorted_list.extend(next_sort(buckets[i]))
+    return sorted_list
+
+def next_sort(arr):
+    # We will use insertion sort here.
+    for i in range(1, len(arr)):
+        j = i - 1
+        key = arr[i]
+        while arr[j] > key and j >= 0:
+            arr[j+1] = arr[j]
+            j = j - 1
+        arr[j + 1] = key
+    return arr
diff --git a/algorithms/sort/shell_sort.py b/algorithms/sort/shell_sort.py
new file mode 100644
index 0000000..61f5f61
--- /dev/null
+++ b/algorithms/sort/shell_sort.py
@@ -0,0 +1,21 @@
+def shell_sort(arr):
+    ''' Shell Sort
+        Complexity: O(n^2)
+    '''
+    n = len(arr)
+    # Initialize size of the gap
+    gap = n//2
+    
+    while gap > 0:
+        y_index = gap
+        while y_index < len(arr):
+            y = arr[y_index]
+            x_index = y_index - gap
+            while x_index >= 0 and y < arr[x_index]:
+                arr[x_index + gap] = arr[x_index]
+                x_index = x_index - gap
+            arr[x_index + gap] = y
+            y_index = y_index + 1
+        gap = gap//2
+        
+    return arr


Test patch:
diff --git a/tests/test_sort.py b/tests/test_sort.py
index 07d13c8..43d5bf2 100644
--- a/tests/test_sort.py
+++ b/tests/test_sort.py
@@ -6,7 +6,9 @@ from algorithms.sort import (
     insertion_sort,
     merge_sort,
     quick_sort,
-    selection_sort
+    selection_sort,
+    bucket_sort,
+    shell_sort
 )
 
 import unittest
@@ -49,6 +51,15 @@ class TestSuite(unittest.TestCase):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          selection_sort([1, 5, 65, 23, 57, 1232]))
 
+    def test_bucket_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                        bucket_sort([1, 5, 65, 23, 57, 1232]))
+
+    def test_shell_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                        shell_sort([1, 5, 65, 23, 57, 1232]))
+                                          
+
 
 if __name__ == "__main__":
     unittest.main()