Repository: keon/algorithms
Pull request #333 (2018-06-07 13:14:43)

Added simulation features in insertion & selection sorts

keon: could you attach how the output looks?
coveralls: ## Pull Request Test Coverage Report for [Build 545](https://coveralls.io/builds/17371161)

* **6** of **10**   **(60.0%)**  changed or added relevant lines in **2** files are covered.
* **2** unchanged lines in **1** file lost coverage.
* Overall coverage decreased (**-0.08%**) to **69.254%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/sort/insertion_sort.py](https://coveralls.io/builds/17371161/source?filename=algorithms%2Fsort%2Finsertion_sort.py#L6) | 3 | 5 | 60.0%
| [algorithms/sort/selection_sort.py](https://coveralls.io/builds/17371161/source?filename=algorithms%2Fsort%2Fselection_sort.py#L6) | 3 | 5 | 60.0%
<!-- | **Total:** | **6** | **10** | **60.0%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/sort/top_sort.py](https://coveralls.io/builds/17371161/source?filename=algorithms%2Fsort%2Ftop_sort.py#L41) | 2 | 90.38% |
<!-- | **Total:** | **2** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17371161/badge)](https://coveralls.io/builds/17371161) |
| :-- | --: |
| Change from base [Build 544](https://coveralls.io/builds/17370030): |  -0.08% |
| Covered Lines: | 3212 |
| Relevant Lines: | 4638 |

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

lg970325: For example, if list = [3, 1, 2, 4, 5]
If you execute insertion_sort(list,True),
[3,1,2,4,5]
[1,3,2,4,5]
[1,2,3,4,5]

If list = [5, 1, 2, 3, 4]
If you execute selection_sort(list,True),
[5,1,2,3,4]
[1,5,2,3,4]
[1,2,5,3,4]
[1,2,3,5,4]
[1,2,3,4,5]

Patch:
diff --git a/README.md b/README.md
index 69b550d..8cbf568 100644
--- a/README.md
+++ b/README.md
@@ -2,6 +2,7 @@
 
 English | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md)
 
+[![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 [![Coverage Status](https://coveralls.io/repos/github/keon/algorithms/badge.svg?branch=master)](https://coveralls.io/github/keon/algorithms?branch=master)
@@ -229,11 +230,13 @@ 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)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
+    - [pancake_sort](algorithms/sort/pancake_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
     - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
diff --git a/README_CN.md b/README_CN.md
index 0f5793e..43032d9 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -2,6 +2,7 @@
 
 [English](README.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md)
 
+[![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 [![Coverage Status](https://coveralls.io/repos/github/keon/algorithms/badge.svg?branch=master)](https://coveralls.io/github/keon/algorithms?branch=master)
@@ -215,11 +216,13 @@ 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)
     - [meeting_rooms：会议室](algorithms/sort/meeting_rooms.py)
     - [merge_sort：归并排序](algorithms/sort/merge_sort.py)
+    - [pancake_sort](algorithms/sort/pancake_sort.py)
     - [quick_sort：快速排序](algorithms/sort/quick_sort.py)
     - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort：选择排序](algorithms/sort/selection_sort.py)
diff --git a/README_GE.md b/README_GE.md
index dc493bc..529ce79 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -2,6 +2,7 @@
 
 [English](README.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md) | [한국어](README_KR.md)
 
+[![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 [![Coverage Status](https://coveralls.io/repos/github/keon/algorithms/badge.svg?branch=master)](https://coveralls.io/github/keon/algorithms?branch=master)
@@ -236,11 +237,13 @@ 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)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
+    - [pancake_sort](algorithms/sort/pancake_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
     - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
diff --git a/README_JP.md b/README_JP.md
index 15d244c..f47bec7 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -2,6 +2,7 @@
 
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 日本語 | [한국어](README_KR.md)
 
+[![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 [![Coverage Status](https://coveralls.io/repos/github/keon/algorithms/badge.svg?branch=master)](https://coveralls.io/github/keon/algorithms?branch=master)
@@ -230,11 +231,13 @@ 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)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
+    - [pancake_sort](algorithms/sort/pancake_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
     - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
diff --git a/README_KR.md b/README_KR.md
index 6787988..8487541 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -2,6 +2,7 @@
 
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 한국어 | [日本語](README_JP.md)
 
+[![PyPI version](https://badge.fury.io/py/algorithms.svg)](https://badge.fury.io/py/algorithms)
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
 [![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 [![Coverage Status](https://coveralls.io/repos/github/keon/algorithms/badge.svg?branch=master)](https://coveralls.io/github/keon/algorithms?branch=master)
@@ -226,11 +227,13 @@ 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)
     - [meeting_rooms](algorithms/sort/meeting_rooms.py)
     - [merge_sort](algorithms/sort/merge_sort.py)
+    - [pancake_sort](algorithms/sort/pancake_sort.py)
     - [quick_sort](algorithms/sort/quick_sort.py)
     - [radix_sort](algorithms/sort/radix_sort.py)
     - [selection_sort](algorithms/sort/selection_sort.py)
diff --git a/algorithms/sort/__init__.py b/algorithms/sort/__init__.py
index a7dba9a..fceb3bd 100644
--- a/algorithms/sort/__init__.py
+++ b/algorithms/sort/__init__.py
@@ -3,9 +3,11 @@ from .bogo_sort import *
 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 *
+from .pancake_sort import *
 from .quick_sort import *
 from .selection_sort import *
 from .top_sort import *
diff --git a/algorithms/sort/bubble_sort.py b/algorithms/sort/bubble_sort.py
index 63c6c4f..76c9816 100644
--- a/algorithms/sort/bubble_sort.py
+++ b/algorithms/sort/bubble_sort.py
@@ -17,8 +17,9 @@ def bubble_sort(arr, simulation=False):
     n = len(arr)
     swapped = True
     
+    iteration = 0
     if simulation:
-        print(arr)
+        print("iteration",iteration,":",*arr)
     
     while swapped:
         swapped = False
@@ -27,6 +28,7 @@ def bubble_sort(arr, simulation=False):
                 swap(i - 1, i)
                 swapped = True
                 if simulation:
-                    print(arr)
+                    iteration = iteration + 1
+                    print("iteration",iteration,":",*arr)
                     
     return arr
diff --git a/algorithms/sort/cycle_sort.py b/algorithms/sort/cycle_sort.py
new file mode 100644
index 0000000..6e512c9
--- /dev/null
+++ 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/algorithms/sort/insertion_sort.py b/algorithms/sort/insertion_sort.py
index f6d1ce3..06c8622 100644
--- a/algorithms/sort/insertion_sort.py
+++ b/algorithms/sort/insertion_sort.py
@@ -1,15 +1,25 @@
-def insertion_sort(arr):
+def insertion_sort(arr, simulation=False):
     """ Insertion Sort
         Complexity: O(n^2)
     """
+    
+    iteration = 0
+    if simulation:
+        print("iteration",iteration,":",*arr)
+        
     for i in range(len(arr)):
         cursor = arr[i]
         pos = i
+        
         while pos > 0 and arr[pos - 1] > cursor:
             # Swap the number down the list
             arr[pos] = arr[pos - 1]
             pos = pos - 1
         # Break and do the final swap
         arr[pos] = cursor
+        
+        if simulation:
+                iteration = iteration + 1
+                print("iteration",iteration,":",*arr)
 
     return arr
diff --git a/algorithms/sort/pancake_sort.py b/algorithms/sort/pancake_sort.py
new file mode 100644
index 0000000..19725c0
--- /dev/null
+++ b/algorithms/sort/pancake_sort.py
@@ -0,0 +1,25 @@
+def pancake_sort(arr):
+    """
+    Pancake_sort
+    Sorting a given array
+    mutation of selection sort
+
+    reference: https://www.geeksforgeeks.org/pancake-sorting/
+    
+    Overall time complexity : O(N^2)
+    """
+
+    len_arr = len(arr)
+    if len_arr <= 1:
+        return arr
+    for cur in range(len(arr), 1, -1):
+        #Finding index of maximum number in arr
+        index_max = arr.index(max(arr[0:cur]))
+        if index_max+1 != cur:
+            #Needs moving
+            if index_max != 0:
+                #reverse from 0 to index_max
+                arr[:index_max+1] = reversed(arr[:index_max+1])
+            # Reverse list
+            arr[:cur] = reversed(arr[:cur])
+    return arr
diff --git a/algorithms/sort/selection_sort.py b/algorithms/sort/selection_sort.py
index c5db918..f6d5352 100644
--- a/algorithms/sort/selection_sort.py
+++ b/algorithms/sort/selection_sort.py
@@ -1,13 +1,23 @@
-def selection_sort(arr):
+def selection_sort(arr, simulation=False):
     """ Selection Sort
         Complexity: O(n^2)
     """
+    iteration = 0
+    if simulation:
+        print("iteration",iteration,":",*arr)
+        
     for i in range(len(arr)):
         minimum = i
+        
         for j in range(i + 1, len(arr)):
             # "Select" the correct value
             if arr[j] < arr[minimum]:
                 minimum = j
 
         arr[minimum], arr[i] = arr[i], arr[minimum]
+        
+        if simulation:
+                iteration = iteration + 1
+                print("iteration",iteration,":",*arr)
+            
     return arr


Test patch:
diff --git a/tests/test_sort.py b/tests/test_sort.py
index 7d8ea8a..d77f086 100644
--- a/tests/test_sort.py
+++ b/tests/test_sort.py
@@ -4,9 +4,11 @@ from algorithms.sort import (
     bubble_sort,
     comb_sort,
     counting_sort,
+    cycle_sort,
     max_heap_sort, min_heap_sort,
     insertion_sort,
     merge_sort,
+    pancake_sort,
     quick_sort,
     selection_sort,
     bucket_sort,
@@ -46,6 +48,10 @@ class TestSuite(unittest.TestCase):
         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]))
@@ -60,6 +66,10 @@ class TestSuite(unittest.TestCase):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          merge_sort([1, 5, 65, 23, 57, 1232]))
 
+    def test_pancake_sort(self):
+        self.assertEqual([1, 5, 23, 57, 65, 1232],
+                         pancake_sort([1, 5, 65, 23, 57, 1232]))
+        
     def test_quick_sort(self):
         self.assertEqual([1, 5, 23, 57, 65, 1232],
                          quick_sort([1, 5, 65, 23, 57, 1232]))