Repository: keon/algorithms
Pull request #305 (2018-06-04 04:39:57)

Create linear_search.py in algorithms/search

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

* **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/17300580/badge)](https://coveralls.io/builds/17300580) |
| :-- | --: |
| Change from base [Build 340](https://coveralls.io/builds/17295523): |  0.0% |
| Covered Lines: | 2748 |
| Relevant Lines: | 3002 |

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


Patch:
diff --git a/CONTRIBUTING_KR.md b/CONTRIBUTING_KR.md
new file mode 100644
index 0000000..522f0e5
--- /dev/null
+++ b/CONTRIBUTING_KR.md
@@ -0,0 +1,66 @@
+# 기여 활동
+
+모든 pull request는 환영입니다. 이 저장소에 기여 함으로써, 당신은 [code of conduct](CODE_OF_CONDUCT.md)
+를 준수하는 것에 동의 한 것입니다.
+
+
+## 시작하기 
+
+* 우선 이 저장소를 [fork][fork] 하시고, 이를 사용하기 위해서 다음과 같이 clone 주세요:
+
+    git clone git@github.com:your-username/algorithms.git  
+
+* 그리고 새로운 내용을 더할 branch를 만들어주세요. 예를 들어:  
+  * add_XXX 만약 당신이 새로운 알고리즘이나 자료 구조를 추가 했을 경우.  
+  * fix_XXX 만약 당신이 어떤 알고리즘이나 자료 구조에서 고쳐야할 bug를 발견했을 경우.  
+  * test_XXX 만약 당신이 test/s를 작성한 경우.  
+
+당신은 다음과 같이 기여할 수 있습니다:
+- 새로운 알고리즘을 구현해주세요. 그리고, 그것을 정확히 분류해주세요(e.g. [array](array), [dp](dp), etc).
+만약 당신의 알고리즘이 어떤 섹션에도 포함이 되지 않는다면, 새로운 섹션을 만들어 주세요. 단, 당신의 알고리즘이 제대로 작동하는지
+확인해주세요.  
+- 알고리즘들을 최적화하거나 향상시켜주세요.
+- 문제들에 대해서 다른 해결 법을 추가해주세요.
+- 버그들을 찾거나 고쳐주세요.
+- 알고리즘들을 더 잘 설명하기 위한 새로운 예시들을 추가해주세요.
+- test cases를 추가해주세요.
+
+## Pull Requests
+당신의 fork에 push 하고 pull request를 제출하세요 [submit a pull request][pr].
+
+우리는 이를 검토할 것이며, 변화, 개량, 혹은 대안을 제시할 수 도 있습니다.
+여기에 당신의 pull request가 허용될 가능성을 높여주는 몇몇 요소들이 있습니다:
+
+* 모든 알고리즘들은 **Python 3**로 작성되어야 합니다.
+(몇몇 알고리즘들은 여전히 _python 2_ 로 작성되어져 있습니다. 당신은 이를 Python 3으로 번역함으로써 저희에게 기여 해주실 수도 있습니다.
+[those][issue120] to _Python 3_.)
+* 깔끔하고 이해할 수 있는 코드를 작성해주세요.
+* 코드에 대해 올바르게 주석 처리 해 주시고, 알고리즘이 수행하는 작업에 대해서 [docstrings][docstr]에서 설명해 주세요.
+* 당신은 간단한 예시를 제시함으로써 출력 값에 대하여 설명하실 수도 있습니다.
+* 또한 가능하다면 알고리즘에 대하여, 두 가지의 test cases를 포함 시켜주세요.
+* [good commit message][commit]를 작성해주세요.
+
+
+## Issues
+만약 추가해야 할 알고리즘이 있거나, 현재 저희 프로젝트의 어떤 알고리즘에서 버그가 발견된다면 [new issue][newissue]에 이를 추가해주세요. 새로운 issue를 제안하기 전에 중복된 issue을 발생을 피하기 위해서 [existing issues][issues]를 확인해주세요. 또한, 현재 존재하는 issue를 해결하는 것을 고려해주시거나 issue에 대한 토의에 기여해주세요.
+
+## Collaborators
+저희 협업자 들에게 어떤 도움이나 확인이 필요하다면, 위 주소로 물어봐주세요.
+
+[Keon Kim](https://github.com/keon)
+
+[Rahul Goswami](https://github.com/goswami-rahul)
+
+[Ankit Agarwal](https://github.com/ankit167)
+
+[Hai Hoang Dang](https://github.com/danghai)
+
+[Saad](https://github.com/SaadBenn)
+
+[fork]: https://help.github.com/articles/fork-a-repo/
+[docstr]: https://www.python.org/dev/peps/pep-0257/#multi-line-docstrings
+[commit]: http://tbaggery.com/2008/04/19/a-note-about-git-commit-messages.html
+[pr]: https://github.com/keon/algorithms/compare/
+[newissue]: https://github.com/keon/algorithms/issues/new
+[issue120]: https://github.com/keon/algorithms/issues/120
+[issues]: https://github.com/keon/algorithms/issues/
diff --git a/README.md b/README.md
index 231facd..aff2cd5 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)
@@ -207,6 +208,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [binary_search](algorithms/search/binary_search.py)
     - [first_occurance](algorithms/search/first_occurance.py)
     - [last_occurance](algorithms/search/last_occurance.py)
+    - [linear_search](algorithms/search/linear_search.py)
     - [search_insert](algorithms/search/search_insert.py)
     - [two_sum](algorithms/search/two_sum.py)
     - [search_range](algorithms/search/search_range.py)
@@ -225,6 +227,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/search/__init__.py b/algorithms/search/__init__.py
index cebea34..89bea2d 100644
--- a/algorithms/search/__init__.py
+++ b/algorithms/search/__init__.py
@@ -1,6 +1,7 @@
 from .binary_search import *
 from .first_occurance import *
 from .last_occurance import *
+from .linear_search import *
 from .search_insert import *
 from .two_sum import *
 from .search_range import *
diff --git a/algorithms/search/linear_search.py b/algorithms/search/linear_search.py
new file mode 100644
index 0000000..da4d9b9
--- /dev/null
+++ b/algorithms/search/linear_search.py
@@ -0,0 +1,13 @@
+#
+# Linear search works in any array.
+#
+# T(n): O(n)
+#
+
+def linear_search(array, query):
+    length = len(array)
+    for i in range(length):
+        if array[i] == query:
+            return i
+
+    return -1
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index 665a0d7..d86e2bc 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -6,5 +6,7 @@ from .insertion_sort import *
 from .merge_sort import *
 from .quick_sort import *
 from .selection_sort import *
+from .top_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
diff --git a/algorithms/sort/top_sort.py b/algorithms/sort/top_sort.py
new file mode 100644
index 0000000..b9188bb
--- /dev/null
+++ b/algorithms/sort/top_sort.py
@@ -0,0 +1,66 @@
+GRAY, BLACK = 0, 1
+
+def top_sort_recursive(graph):
+    """ Time complexity is the same as DFS, which is O(V + E)
+        Space complexity: O(V)
+    """
+    order, enter, state = [], set(graph), {}
+    
+    def dfs(node):
+        state[node] = GRAY
+        #print(node)
+        for k in graph.get(node, ()):
+            sk = state.get(k, None)
+            if sk == GRAY:
+                raise ValueError("cycle")
+            if sk == BLACK:
+                continue
+            enter.discard(k)
+            dfs(k)
+        order.append(node)
+        state[node] = BLACK
+        
+    while enter: dfs(enter.pop())
+    return order
+
+def top_sort(graph):
+    """ Time complexity is the same as DFS, which is O(V + E)
+        Space complexity: O(V)
+    """
+    order, enter, state = [], set(graph), {}
+    
+    def is_ready(node):
+        lst = graph.get(node, ())
+        if len(lst) == 0:
+            return True
+        for k in lst:
+            sk = state.get(k, None)
+            if sk == GRAY: 
+                raise ValueError("cycle")
+            if sk != BLACK:
+                return False
+        return True
+        
+    while enter:
+        node = enter.pop()
+        stack = []
+        while True:
+            state[node] = GRAY
+            stack.append(node)
+            for k in graph.get(node, ()):
+                sk = state.get(k, None)
+                if sk == GRAY: 
+                    raise ValueError("cycle")
+                if sk == BLACK: 
+                    continue
+                enter.discard(k)
+                stack.append(k)
+            while stack and is_ready(stack[-1]):
+                node = stack.pop()
+                order.append(node)
+                state[node] = BLACK
+            if len(stack) == 0:
+                break
+            node = stack.pop()
+        
+    return order
diff --git a/algorithms/sort/topsort.py b/algorithms/sort/topsort.py
deleted file mode 100644
index 8341ce9..0000000
--- a/algorithms/sort/topsort.py
+++ /dev/null
@@ -1,60 +0,0 @@
-"""
-Given a list of system packages,
-some packages cannot be installed until the other packages are installed.
-Provide a valid sequence to install all of the packages.
-
-e.g.
-a relies on b
-b relies on c
-
-then a valid sequence is [c, b, a]
-"""
-
-depGraph = {
-
-    "a": ["b"],
-    "b": ["c"],
-    "c": ['e'],
-    'e': [],
-    "d": [],
-    "f": ["e", "d"]
-}
-
-given = ["b", "c", "a", "d", "e", "f"]
-
-
-def ret_deps(visited, start):
-    queue = []
-    out = []
-    queue.append(start)
-    while queue:
-        new_node = queue.pop(0)
-        if new_node not in visited:
-            visited.add(new_node)
-        for child in depGraph[new_node]:
-            queue.append(child)
-            out.append(child)
-    out.append(start)
-    return out
-
-
-def ret_dep_graph():
-    visited = set()
-    out = []
-    # visited.add(given[0])
-    for pac in given:
-        if pac in visited:
-            continue
-        visited.add(pac)
-        # out.append(pac)
-        if pac in depGraph:
-            # find all children
-            for child in depGraph[pac]:
-                if child in visited:
-                    continue
-                out.extend(ret_deps(visited, child))
-        out.append(pac)
-    print(out)
-
-
-ret_dep_graph()


Test patch:
diff --git a/tests/graph/__init__.py b/tests/graph/__init__.py
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/tests/graph/__init__.py
@@ -0,0 +1,1 @@
+
diff --git a/tests/graph/test_topsort.py b/tests/graph/test_topsort.py
new file mode 100644
index 0000000..a308ed3
--- /dev/null
+++ b/tests/graph/test_topsort.py
@@ -0,0 +1,27 @@
+from algorithms.sort import (
+    top_sort, top_sort_recursive
+)
+
+import unittest
+
+class TestSuite(unittest.TestCase):
+    def setUp(self):
+        self.depGraph = {
+                            "a" : [ "b" ],
+                            "b" : [ "c" ],
+                            "c" :  [ 'e'],
+                            'e' : [ 'g' ],
+                            "d" : [ ],
+                            "f" : ["e" , "d"],
+                            "g" : [ ]
+                        }
+        
+    def test_topsort(self):
+        res = top_sort_recursive(self.depGraph)
+        #print(res)
+        self.assertTrue(res.index('g') < res.index('e'))
+        res = top_sort(self.depGraph)
+        self.assertTrue(res.index('g') < res.index('e'))
+
+if __name__ == '__main__':
+    unittest.main()
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_search.py b/tests/test_search.py
index 4567ec5..360397f 100644
--- a/tests/test_search.py
+++ b/tests/test_search.py
@@ -2,6 +2,7 @@ from algorithms.search import (
     binary_search, binary_search_recur,
     first_occurance,
     last_occurance,
+    linear_search,
     search_insert,
     two_sum, two_sum1, two_sum2,
     search_range,
@@ -44,6 +45,13 @@ class TestSuite(unittest.TestCase):
         self.assertEqual(None, last_occurance(array, 7))
         self.assertEqual(0, last_occurance(array, 1))
         self.assertEqual(13, last_occurance(array, 6))
+        
+    def test_linear_search(self):
+        array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
+        self.assertEqual(6, linear_search(array, 4))
+        self.assertEqual(10, linear_search(array, 5))
+        self.assertEqual(-1, linear_search(array, 7))
+        self.assertEqual(-1, linear_search(array, -1))
 
     def test_search_insert(self):
         array = [1,3,5,6]
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__":