added bucket_sort.py & shell_sort.py (keon#296)

geon0325 · goswami-rahul · commit b39f4e52d06d · 2018-06-02T02:29:31.000+05:30
* Create bucket_sort.py

* Create shell_sort.py

* Update test_sort.py

* Update __init__.py
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
@@ -6,3 +6,5 @@
 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
@@ -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
@@ -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
diff --git a/tests/test_sort.py b/tests/test_sort.py
@@ -6,7 +6,9 @@
     insertion_sort,
     merge_sort,
     quick_sort,
-    selection_sort
+    selection_sort,
+    bucket_sort,
+    shell_sort
 )
 
 import unittest
@@ -49,6 +51,15 @@ def test_selection_sort(self):
         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()
