Created radix_sort.py in algorithms/sort (keon#303)

aig031 · goswami-rahul · commit 4a3cbb70bb25 · 2018-06-04T18:12:09.000+05:30
* Create radix_sort.py

* Update test_sort.py

* Update __init__.py

* Update radix_sort.py

* Update radix_sort.py

* Update README.md

* Update README_CN.md

* Update README_GE.md

* Update README_JP.md

* Update README_KR.md
diff --git a/README.md b/README.md
@@ -226,6 +226,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
+    - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
     - [shell_sort](algorithms/sort/shell_sort.py)
     - [sort_colors](algorithms/sort/sort_colors.py)
diff --git a/README_CN.md b/README_CN.md
@@ -208,6 +208,7 @@ pip3 uninstall -y algorithms
     - [meeting_rooms：会议室](algorithms/sort/meeting_rooms.py)
     - [merge_sort：归并排序](algorithms/sort/merge_sort.py)
     - [quick_sort：快速排序](algorithms/sort/quick_sort.py)
+    - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort：选择排序](algorithms/sort/selection_sort.py)
     - [shell_sort](algorithms/sort/shell_sort.py)
     - [sort_colors：颜色排序](algorithms/sort/sort_colors.py)
diff --git a/README_GE.md b/README_GE.md
@@ -233,6 +233,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
+    - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
     - [shell_sort](algorithms/sort/shell_sort.py)
     - [sort_colors](algorithms/sort/sort_colors.py)
diff --git a/README_JP.md b/README_JP.md
@@ -223,6 +223,7 @@ if __name__ == "__main__":
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
+    - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
     - [shell_sort](algorithms/sort/shell_sort.py)
     - [sort_colors](algorithms/sort/sort_colors.py)
diff --git a/README_KR.md b/README_KR.md
@@ -218,6 +218,7 @@ if __name__ == "__main__":
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
+    - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
     - [sort_colors](algorithms/sort/sort_colors.py)
     - [topsort](algorithms/sort/topsort.py)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
@@ -8,3 +8,4 @@
 from .selection_sort import *
 from .bucket_sort import *
 from .shell_sort import *
+from .radix_sort import *
diff --git a/algorithms/sort/radix_sort.py b/algorithms/sort/radix_sort.py
@@ -0,0 +1,26 @@
+"""
+radix sort
+complexity: O(nk) . n is the size of input list and k is the digit length of the number
+"""
+def radix_sort(arr):
+    is_done = False
+    position = 1
+
+    while not is_done:
+        queue_list = [list() for _ in range(10)]
+        is_done = True
+
+        for num in arr:
+            digit_number = num // position % 10
+            queue_list[digit_number].append(num)
+            if is_done and digit_number > 0:
+                is_done = False
+
+        index = 0
+        for numbers in queue_list:
+            for num in numbers:
+                arr[index] = num
+                index += 1
+
+        position *= 10
+    return arr
diff --git a/tests/test_sort.py b/tests/test_sort.py
@@ -8,7 +8,8 @@
     quick_sort,
     selection_sort,
     bucket_sort,
-    shell_sort
+    shell_sort,
+    radix_sort
 )
 
 import unittest
@@ -59,6 +60,10 @@ def test_shell_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         shell_sort([1, 5, 65, 23, 57, 1232]))
                                           
+    def test_radix_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                        radix_sort([1, 5, 65, 23, 57, 1232]))
+                                          
 
 
 if __name__ == "__main__":
