Created cycle_sort.py in algorithms/sort (keon#338)

9967han · goswami-rahul · commit 409ae684a740 · 2018-06-08T11:45:38.000+05:30
* Create cycle_sort.py

* Update test_sort.py

* Update __init__.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
@@ -230,6 +230,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)
+    - [cycle_sort](algorithms/sort/cycle_sort.py)
     - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
diff --git a/README_CN.md b/README_CN.md
@@ -216,6 +216,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)
+    - [cycle_sort](algorithms/sort/cycle_sort.py)
     - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort：堆排序](algorithms/sort/heap_sort.py)
     - [insertion_sort：插入排序](algorithms/sort/insertion_sort.py)
diff --git a/README_GE.md b/README_GE.md
@@ -237,6 +237,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)
+    - [cycle_sort](algorithms/sort/cycle_sort.py)
     - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
diff --git a/README_JP.md b/README_JP.md
@@ -231,6 +231,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)
+    - [cycle_sort](algorithms/sort/cycle_sort.py)
     - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
diff --git a/README_KR.md b/README_KR.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)
+    - [cycle_sort](algorithms/sort/cycle_sort.py)
     - [gnome_sort](algorithms/sort/gnome_sort.py)
     - [heap_sort](algorithms/sort/heap_sort.py)
     - [insertion_sort](algorithms/sort/insertion_sort.py)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
@@ -3,6 +3,7 @@
 from .bubble_sort import *
 from .comb_sort import *
 from .counting_sort import *
+from .cycle_sort import *
 from .heap_sort import *
 from .insertion_sort import *
 from .merge_sort import *
diff --git a/algorithms/sort/cycle_sort.py b/algorithms/sort/cycle_sort.py
@@ -0,0 +1,46 @@
+def cycle_sort(arr):
+    """
+    cycle_sort
+    This is based on the idea that the permutations to be sorted
+    can be decomposed into cycles,
+    and the results can be individually sorted by cycling.
+    
+    reference: https://en.wikipedia.org/wiki/Cycle_sort
+    
+    Average time complexity : O(N^2)
+    Worst case time complexity : O(N^2)
+    """
+    len_arr = len(arr)
+    # Finding cycle to rotate.
+    for cur in range(len_arr - 1):
+        item = arr[cur]
+
+        # Finding an indx to put items in.
+        index = cur
+        for i in range(cur + 1, len_arr):
+            if arr[i] < item:
+                index += 1
+
+        # Case of there is not a cycle
+        if index == cur:
+            continue
+
+        # Putting the item immediately right after the duplicate item or on the right.
+        while item == arr[index]:
+            index += 1
+        arr[index], item = item, arr[index]
+
+        # Rotating the remaining cycle.
+        while index != cur:
+
+            # Finding where to put the item.
+            index = cur
+            for i in range(cur + 1, len_arr):
+                if arr[i] < item:
+                    index += 1
+
+            # After item is duplicated, put it in place or put it there.
+            while item == arr[index]:
+                index += 1
+            arr[index], item = item, arr[index]
+    return arr
diff --git a/tests/test_sort.py b/tests/test_sort.py
@@ -4,6 +4,7 @@
     bubble_sort,
     comb_sort,
     counting_sort,
+    cycle_sort,
     max_heap_sort, min_heap_sort,
     insertion_sort,
     merge_sort,
@@ -47,6 +48,10 @@ def test_counting_sort(self):
         self.assertEqual([-1232, -65, -57, -23, -5, -1],
                          counting_sort([-1, -5, -65, -23, -57, -1232]))
 
+    def test_cycle_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                         cycle_sort([1, 5, 65, 23, 57, 1232]))
+
     def test_heap_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          max_heap_sort([1, 5, 65, 23, 57, 1232]))
