summaryrefslogtreecommitdiff
path: root/sort
diff options
context:
space:
mode:
Diffstat (limited to 'sort')
-rw-r--r--sort/pancakesort.hs30
-rw-r--r--sort/shell.adb33
-rw-r--r--sort/shell.ads16
-rw-r--r--sort/stooge.adb41
-rw-r--r--sort/stooge.ads16
5 files changed, 136 insertions, 0 deletions
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;
+