Created gnome sort in sort algorithm (keon#313)

geon0325 · goswami-rahul · commit 36c1af414476 · 2018-06-06T15:08:36.000+05:30
* Create gnome_sort.py

* Update __init__.py

* Update test_sort.py

* Update README.md

* Update README_CN.md

* Update README_GE.md

* Update README_JP.md

* Update README_KR.md

* Update gnome_sort.py
diff --git a/README.md b/README.md
@@ -228,6 +228,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
     - [comb_sort](algorithms/sort/comb_sort.py)
     - [counting_sort](algorithms/sort/counting_sort.py)
+    - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
diff --git a/README_CN.md b/README_CN.md
@@ -212,6 +212,7 @@ pip3 uninstall -y algorithms
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
     - [comb_sort：梳排序](algorithms/sort/comb_sort.py)
     - [counting_sort：计数排序](algorithms/sort/counting_sort.py)
+    - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort：堆排序](algorithms/sort/heap_sort.py)
     - [insertion_sort：插入排序](algorithms/sort/insertion_sort.py)
     - [meeting_rooms：会议室](algorithms/sort/meeting_rooms.py)
diff --git a/README_GE.md b/README_GE.md
@@ -233,6 +233,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
     - [comb_sort](algorithms/sort/comb_sort.py)
     - [counting_sort](algorithms/sort/counting_sort.py)
+    - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
diff --git a/README_JP.md b/README_JP.md
@@ -227,6 +227,7 @@ if __name__ == "__main__":
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
     - [comb_sort](algorithms/sort/comb_sort.py)
     - [counting_sort](algorithms/sort/counting_sort.py)
+    - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
diff --git a/README_KR.md b/README_KR.md
@@ -223,6 +223,7 @@ if __name__ == "__main__":
     - [cocktail_shaker_sort](algorithms/sort/cocktail_shaker_sort.py)
     - [comb_sort](algorithms/sort/comb_sort.py)
     - [counting_sort](algorithms/sort/counting_sort.py)
+    - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
@@ -11,4 +11,5 @@
 from .bucket_sort import *
 from .shell_sort import *
 from .radix_sort import *
+from .gnome_sort import *
 from .cocktail_shaker_sort import *
diff --git a/algorithms/sort/gnome_sort.py b/algorithms/sort/gnome_sort.py
@@ -0,0 +1,19 @@
+"""
+
+Gnome Sort
+Best case performance is O(n)
+Worst case performance is O(n^2)
+
+"""
+
+
+def gnome_sort(arr):
+    n = len(arr)
+    index = 0
+    while index < n:
+        if index == 0 or arr[index] >= arr[index-1]:
+            index = index + 1
+        else:
+            arr[index], arr[index-1] = arr[index-1], arr[index]
+            index = index - 1
+    return arr
diff --git a/tests/test_sort.py b/tests/test_sort.py
@@ -11,7 +11,8 @@
     bucket_sort,
     shell_sort,
     radix_sort,
-    cocktail_shaker_sort
+    gnome_sort,
+    cocktail_shaker_sort,
 )
 
 import unittest
@@ -69,7 +70,11 @@ def test_shell_sort(self):
     def test_radix_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         radix_sort([1, 5, 65, 23, 57, 1232]))
-     
+    
+    def test_gnome_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                         gnome_sort([1, 5, 65, 23, 57, 1232]))
+                                          
     def test_cocktail_shaker_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                         cocktail_shaker_sort([1, 5, 65, 23, 57, 1232]))
