Added bubble, quick, selection, merge, gnome sorting algorithms

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;
+