summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bubble.adb64
-rw-r--r--bubble.ads17
-rw-r--r--gnomesort.hs19
-rw-r--r--mergesort.hs19
-rw-r--r--quick.adb49
-rw-r--r--quick.ads16
-rw-r--r--quicksort.hs12
-rw-r--r--selection.adb42
-rw-r--r--selection.ads16
9 files changed, 254 insertions, 0 deletions
diff --git a/bubble.adb b/bubble.adb
new file mode 100644
index 0000000..f4f2485
--- /dev/null
+++ b/bubble.adb
@@ -0,0 +1,64 @@
+
+
+package body Bubble 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
+ Swapped : Boolean;
+ begin
+ if Arr'Length <= 1 then
+ return;
+ end if;
+
+ loop
+ Swapped := False;
+
+ for I in Index_T range Arr'First .. Index_T'Pred(Arr'Last) loop
+ if Arr(I) > Arr(Index_T'Succ(I)) then
+ Swap( Arr(I), Arr(Index_T'Succ(I)) );
+ Swapped := True;
+ end if;
+ end loop;
+
+ exit when not Swapped;
+ end loop;
+
+ end Sort;
+
+
+ procedure Optimized(Arr : in out Array_T) is
+ N, NewN : Index_T;
+ begin
+ if Arr'Length <= 1 then
+ return;
+ end if;
+
+ N := Arr'Last;
+ loop
+ NewN := Arr'First;
+
+ for I in Index_T range Arr'First .. Index_T'Pred(N) loop
+ if Arr(I) > Arr(Index_T'Succ(I)) then
+ Swap( Arr(I), Arr(Index_T'Succ(I)) );
+ NewN := I;
+ end if;
+ end loop;
+
+ N := NewN;
+ exit when N = Arr'First;
+ end loop;
+
+ end Optimized;
+
+
+end Bubble;
+
diff --git a/bubble.ads b/bubble.ads
new file mode 100644
index 0000000..529c5c6
--- /dev/null
+++ b/bubble.ads
@@ -0,0 +1,17 @@
+
+
+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 Bubble is
+
+ procedure Sort(Arr : in out Array_T);
+ procedure Optimized(Arr : in out Array_T);
+
+end Bubble;
+
diff --git a/gnomesort.hs b/gnomesort.hs
new file mode 100644
index 0000000..2a9b9ce
--- /dev/null
+++ b/gnomesort.hs
@@ -0,0 +1,19 @@
+
+
+
+gnomeSort :: Ord a => [a] -> [a]
+gnomeSort list = doGnomeSort list 1
+
+
+
+doGnomeSort :: Ord a => [a] -> Int -> [a]
+doGnomeSort list pos | pos >= length list = list
+doGnomeSort list pos =
+ if (list !! pos) >= (list !! (pos - 1))
+ then doGnomeSort list (pos + 1)
+ else let list' = (take (pos - 1) list) ++ [list !! pos] ++
+ [list !! (pos - 1)] ++ (drop (pos + 1) list)
+ pos' = if pos > 1 then pos - 1 else pos
+ in doGnomeSort list' pos'
+
+
diff --git a/mergesort.hs b/mergesort.hs
new file mode 100644
index 0000000..5c140b3
--- /dev/null
+++ b/mergesort.hs
@@ -0,0 +1,19 @@
+
+
+
+mergeSort :: Ord a => [a] -> [a]
+mergeSort x | length x <= 1 = x
+mergeSort x =
+ let n = (length x) `div` 2
+ left = mergeSort (take n x)
+ right = mergeSort (drop n x)
+ in merge left right
+
+
+
+merge :: Ord a => [a] -> [a] -> [a]
+merge [] y = y
+merge x [] = x
+merge (x:xs) (y:ys) = if x <= y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)
+
+
diff --git a/quick.adb b/quick.adb
new file mode 100644
index 0000000..4586b3b
--- /dev/null
+++ b/quick.adb
@@ -0,0 +1,49 @@
+
+
+package body Quick is
+
+
+ procedure Swap(A, B : in out Element_T) is
+ Temp : Element_T;
+ begin
+ Temp := A;
+ A := B;
+ B := Temp;
+ end Swap;
+
+
+ procedure In_Place(Arr : in out Array_T) is
+ Pivot, Left, Right : Index_T;
+ begin
+ if Arr'Length <= 1 then
+ return;
+ end if;
+
+ Pivot := Arr'First;
+ Left := Index_T'Succ(Pivot);
+ Right := Arr'Last;
+
+ loop
+ while not (Arr(Left) > Arr(Pivot)) and Left < Arr'Last loop
+ Left := Index_T'Succ(Left);
+ end loop;
+ while Arr(Right) > Arr(Pivot) and Right > Arr'First loop
+ Right := Index_T'Pred(Right);
+ end loop;
+ exit when Left >= Right;
+ Swap(Arr(Left), Arr(Right));
+ end loop;
+
+ Swap(Arr(Pivot), Arr(Right));
+
+ if Right > Arr'First then
+ In_Place( Arr(Arr'First .. Index_T'Pred(Right)) );
+ end if;
+ if Right < Arr'Last then
+ In_Place( Arr(Index_T'Succ(Right) .. Arr'Last) );
+ end if;
+ end In_Place;
+
+
+end Quick;
+
diff --git a/quick.ads b/quick.ads
new file mode 100644
index 0000000..e406d51
--- /dev/null
+++ b/quick.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 Quick is
+
+ procedure In_Place(Arr : in out Array_T);
+
+end Quick;
+
diff --git a/quicksort.hs b/quicksort.hs
new file mode 100644
index 0000000..78330f3
--- /dev/null
+++ b/quicksort.hs
@@ -0,0 +1,12 @@
+
+
+
+quickSort :: Ord a => [a] -> [a]
+quickSort [] = []
+quickSort (x:xs) =
+ let less = [ a | a <- xs, a < x ]
+ equal = [ b | b <- (x:xs), b == x ]
+ greater = [ c | c <- xs, c > x ]
+ in quickSort less ++ equal ++ quickSort greater
+
+
diff --git a/selection.adb b/selection.adb
new file mode 100644
index 0000000..1b49769
--- /dev/null
+++ b/selection.adb
@@ -0,0 +1,42 @@
+
+
+package body Selection is
+
+
+ procedure Swap(A, B : in out Element_T) is
+ Temp : Element_T;
+ begin
+ Temp := A;
+ A := B;
+ B := Temp;
+ end Swap;
+
+
+ function Find_Largest(Arr : in Array_T) return Index_T is
+ Max : Index_T;
+ begin
+ Max := Arr'First;
+ for P in Index_T range Index_T'Succ(Arr'First) .. Arr'Last loop
+ if Arr(P) > Arr(Max) then
+ Max := P;
+ end if;
+ end loop;
+ return Max;
+ end Find_Largest;
+
+
+ procedure Sort(Arr : in out Array_T) is
+ Largest : Index_T;
+ begin
+ if Arr'Length <= 1 then
+ return;
+ end if;
+
+ Largest := Find_Largest(Arr);
+ Swap( Arr(Arr'Last), Arr(Largest) );
+ Sort( Arr(Arr'First .. Index_T'Pred(Arr'Last)) );
+ end Sort;
+
+
+end Selection;
+
diff --git a/selection.ads b/selection.ads
new file mode 100644
index 0000000..af085af
--- /dev/null
+++ b/selection.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 Selection is
+
+ procedure Sort(Arr : in out Array_T);
+
+end Selection;
+
generated by cgit (git 2.30.0) at 2024-12-22 13:22:22 +0000