From faeec19d3a971efdc94e86c5fc2d59239b04e84a Mon Sep 17 00:00:00 2001
From: Jed Barber <jjbarber@y7mail.com>
Date: Sun, 18 Oct 2015 13:19:48 +1100
Subject: Added shell, stooge, pancake sorts

---
 sort/pancakesort.hs | 30 ++++++++++++++++++++++++++++++
 sort/shell.adb      | 33 +++++++++++++++++++++++++++++++++
 sort/shell.ads      | 16 ++++++++++++++++
 sort/stooge.adb     | 41 +++++++++++++++++++++++++++++++++++++++++
 sort/stooge.ads     | 16 ++++++++++++++++
 5 files changed, 136 insertions(+)
 create mode 100644 sort/pancakesort.hs
 create mode 100644 sort/shell.adb
 create mode 100644 sort/shell.ads
 create mode 100644 sort/stooge.adb
 create mode 100644 sort/stooge.ads

diff --git a/sort/pancakesort.hs b/sort/pancakesort.hs
new file mode 100644
index 0000000..30993ba
--- /dev/null
+++ b/sort/pancakesort.hs
@@ -0,0 +1,30 @@
+
+
+
+pancakeSort :: Ord a => [a] -> [a]
+pancakeSort [] = []
+pancakeSort cakeStack =
+    let selectedCake = indexOfLargest cakeStack
+        cakeStack' = (doFlip (length cakeStack)) . (doFlip selectedCake) $ cakeStack
+    in (pancakeSort (init cakeStack')) ++ [last cakeStack']
+
+
+
+indexOfLargest :: Ord a => [a] -> Int
+indexOfLargest (x:xs) =
+    let f m i j y = if length y == 0
+                        then i
+                        else if (head y) > m
+                                then f (head y) j (j+1) (tail y)
+                                else f m i (j+1) (tail y)
+    in f x 0 1 xs
+
+
+
+doFlip :: Int -> [a] -> [a]
+doFlip depth list =
+    let prefix = take (depth + 1) list
+        rest = drop (depth + 1) list
+    in (reverse prefix) ++ rest
+
+
diff --git a/sort/shell.adb b/sort/shell.adb
new file mode 100644
index 0000000..6e9cc22
--- /dev/null
+++ b/sort/shell.adb
@@ -0,0 +1,33 @@
+
+
+package body Shell is
+
+
+    -- sequence from Marcin Ciura, 2001
+    Gaps : array (Positive range 1 .. 8) of Integer := (701, 301, 132, 57, 23, 10, 4, 1);
+
+
+    procedure Sort(Arr : in out Array_T) is
+        Temp : Element_T;
+        Place : Integer;
+    begin
+        if Arr'Length <= 1 then
+            return;
+        end if;
+
+        for G of Gaps loop
+            for I in Integer range (Index_T'Pos(Arr'First) + G) .. Index_T'Pos(Arr'Last) loop
+                Place := I;
+                Temp := Arr(Index_T'Val(Place));
+                while Place >= (Index_T'Pos(Arr'First) + G) and then Arr(Index_T'Val(Place - G)) > Temp loop
+                    Arr(Index_T'Val(Place)) := Arr(Index_T'Val(Place - G));
+                    Place := Place - G;
+                end loop;
+                Arr(Index_T'Val(Place)) := Temp;
+            end loop;
+        end loop;
+    end Sort;
+
+
+end Shell;
+
diff --git a/sort/shell.ads b/sort/shell.ads
new file mode 100644
index 0000000..0ce3cb4
--- /dev/null
+++ b/sort/shell.ads
@@ -0,0 +1,16 @@
+
+
+generic
+
+    type Index_T is (<>);
+    type Element_T is private;
+    type Array_T is array (Index_T range <>) of Element_T;
+
+    with function ">"(X, Y : in Element_T) return Boolean is <>;
+
+package Shell is
+
+    procedure Sort(Arr : in out Array_T);
+
+end Shell;
+
diff --git a/sort/stooge.adb b/sort/stooge.adb
new file mode 100644
index 0000000..fb1077d
--- /dev/null
+++ b/sort/stooge.adb
@@ -0,0 +1,41 @@
+
+with Ada.Text_IO; use Ada.Text_IO;
+
+package body Stooge is
+
+
+    procedure Swap(A, B : in out Element_T) is
+        Temp : Element_T;
+    begin
+        Temp := A;
+        A := B;
+        B := Temp;
+    end Swap;
+
+
+    procedure Sort(Arr : in out Array_T) is
+    begin
+        if Arr'Length <= 1 then
+            return;
+        end if;
+
+        if Arr(Arr'First) > Arr(Arr'Last) then
+            Swap(Arr(Arr'First), Arr(Arr'Last));
+        end if;
+
+        if Arr'Length >= 3 then
+            declare
+                Third : Integer := Arr'Length / 3;
+                Arr_One_Third : Index_T := Index_T'Val(Index_T'Pos(Arr'First) + Third);
+                Arr_Two_Third : Index_T := Index_T'Val(Index_T'Pos(Arr'Last) - Third);
+            begin
+                Sort(Arr(Arr'First .. Arr_Two_Third));
+                Sort(Arr(Arr_One_Third .. Arr'Last));
+                Sort(Arr(Arr'First .. Arr_Two_Third));
+            end;
+        end if;
+    end Sort;
+
+
+end Stooge;
+
diff --git a/sort/stooge.ads b/sort/stooge.ads
new file mode 100644
index 0000000..c2e088e
--- /dev/null
+++ b/sort/stooge.ads
@@ -0,0 +1,16 @@
+
+
+generic
+
+    type Index_T is (<>);
+    type Element_T is private;
+    type Array_T is array (Index_T range <>) of Element_T;
+
+    with function ">"(X, Y : in Element_T) return Boolean is <>;
+
+package Stooge is
+
+    procedure Sort(Arr : in out Array_T);
+
+end Stooge;
+
-- 
cgit