Created pancake_sort.py in algorithms/sorts (keon#336)

9967han · Hai Hoang Dang · commit f9f874699357 · 2018-06-07T11:03:09.000-07:00
* Update README.md

* Update README_CN.md

* Update README_GE.md

* Update README_JP.md

* Update README_KR.md

* Update test_sort.py

* Create pancake_sort.py

* Update __init__.py
diff --git a/README.md b/README.md
@@ -235,6 +235,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [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
@@ -221,6 +221,7 @@ pip3 uninstall -y algorithms
     - [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
@@ -242,6 +242,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [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
@@ -236,6 +236,7 @@ if __name__ == "__main__":
     - [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
@@ -232,6 +232,7 @@ if __name__ == "__main__":
     - [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
@@ -6,6 +6,7 @@
 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/pancake_sort.py 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/tests/test_sort.py b/tests/test_sort.py
@@ -7,6 +7,7 @@
     max_heap_sort, min_heap_sort,
     insertion_sort,
     merge_sort,
+    pancake_sort,
     quick_sort,
     selection_sort,
     bucket_sort,
@@ -60,6 +61,10 @@ def test_merge_sort(self):
         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]))
