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

* Create bucket_sort.py * Create shell_sort.py * Update test_sort.py * Update __init__.py
keon · Jun 1, 2018 · b39f4e5 · b39f4e5
1 parent 91aee95
commit b39f4e5
Show file tree

Hide file tree

Showing 4 changed files with 63 additions and 1 deletion.
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()