Repository: keon/algorithms
Pull request #303 (2018-06-04 00:10:35)

Created radix_sort.py in algorithms/sort
It seems like there are no radix_sort in the sort file, so I added it.

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

* **0** of **0**   changed or added relevant lines in **0** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **91.539%**

---



|  Totals | [![Coverage Status](https://coveralls.io/builds/17298999/badge)](https://coveralls.io/builds/17298999) |
| :-- | --: |
| Change from base [Build 340](https://coveralls.io/builds/17295523): |  0.0% |
| Covered Lines: | 2748 |
| Relevant Lines: | 3002 |

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

aig031: I change test_sort too!

Patch:
diff --git a/README.md b/README.md
index 231facd..c6011f8 100644
--- a/README.md
+++ b/README.md
@@ -172,6 +172,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [valid_sudoku](algorithms/map/valid_sudoku.py)
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
+    - [combination](algorithms/maths/combination.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
@@ -225,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
index 130898a..91451ff 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -164,6 +164,7 @@ pip3 uninstall -y algorithms
     - [valid_sudoku：有效数独](algorithms/map/valid_sudoku.py)
 - [math：数学问题](algorithms/maths)
     - [extended_gcd：扩展欧几里得算法](algorithms/maths/extended_gcd.py)
+    - [combination](algorithms/maths/combination.py)
     - [gcd/lcm：最大公约数和最小公倍数](algorithms/maths/gcd.py)
     - [prime_test：主要测试](algorithms/maths/prime_test.py)
     - [primes_sieve_of_eratosthenes：埃拉托色尼的质数筛](algorithms/maths/primes_sieve_of_eratosthenes.py)
@@ -207,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
index 5380e65..89922c5 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -179,6 +179,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [valid_sudoku](algorithms/map/valid_sudoku.py)
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
+    - [combination](algorithms/maths/combination.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
@@ -232,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
index f50d6df..3083d72 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -1,6 +1,6 @@
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 日本語 | [한국어](README_KR.md)
 
-pythonのデータ構造とアルゴリズム
+Pythonのデータ構造とアルゴリズム
 =========================================
 
 Python 3で開発された簡単で明確なデータ構造とアルゴリズムの例を紹介します。
@@ -169,6 +169,7 @@ if __name__ == "__main__":
     - [valid_sudoku](algorithms/map/valid_sudoku.py)
 - [maths : 数学](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
+    - [combination](algorithms/maths/combination.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
@@ -222,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
index a2b408a..0b4c599 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -165,6 +165,7 @@ if __name__ == "__main__":
     - [valid_sudoku](algorithms/map/valid_sudoku.py)
 - [maths : 수학 계산](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
+    - [combination](algorithms/maths/combination.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
@@ -217,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/maths/__init__.py b/algorithms/maths/__init__.py
index 6716384..d791ad8 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -9,3 +9,4 @@ from .primes_sieve_of_eratosthenes import *
 from .pythagoras import *
 from .rabin_miller import *
 from .rsa import *
+from .combination import *
diff --git a/algorithms/maths/combination.py b/algorithms/maths/combination.py
new file mode 100644
index 0000000..ea9e4b3
--- /dev/null
+++ b/algorithms/maths/combination.py
@@ -0,0 +1,6 @@
+def combination(n, r):
+    # This function calculates nCr
+    if n == r or r == 0:
+        return 1
+    else:
+        return combination(n-1, r-1) + combination(n-1, r)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index 665a0d7..39eb147 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -8,3 +8,4 @@ from .quick_sort import *
 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
new file mode 100644
index 0000000..fee0f2f
--- /dev/null
+++ 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


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index afafd2e..fbf0772 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -9,7 +9,8 @@ from algorithms.maths import (
     primes,
     pythagoras,
     is_prime,
-    encrypt, decrypt, generate_key
+    encrypt, decrypt, generate_key,
+    combination
 )
 
 import unittest
@@ -202,6 +203,17 @@ class TestRSA(unittest.TestCase):
     #         dec = decrypt(en, d, n)
     #         self.assertEqual(data,dec)
 
+class TestCombination(unittest.TestCase):
+    """[summary]
+    Test for the file rsa.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
 
+    def test_combination(self):
+        self.assertEqual(10, combination(5, 2))
+        self.assertEqual(252, combination(10, 5))
+        
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_sort.py b/tests/test_sort.py
index 43d5bf2..4665259 100644
--- a/tests/test_sort.py
+++ b/tests/test_sort.py
@@ -8,7 +8,8 @@ from algorithms.sort import (
     quick_sort,
     selection_sort,
     bucket_sort,
-    shell_sort
+    shell_sort,
+    radix_sort
 )
 
 import unittest
@@ -59,6 +60,10 @@ class TestSuite(unittest.TestCase):
         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__":