From 3e30658ec5ca3ade4f9295129729127a30b4addf Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Wed, 14 Oct 2015 12:21:23 +1100 Subject: Added bubble, quick, selection, merge, gnome sorting algorithms --- bubble.adb | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bubble.ads | 17 ++++++++++++++++ gnomesort.hs | 19 ++++++++++++++++++ mergesort.hs | 19 ++++++++++++++++++ quick.adb | 49 +++++++++++++++++++++++++++++++++++++++++++++ quick.ads | 16 +++++++++++++++ quicksort.hs | 12 +++++++++++ selection.adb | 42 +++++++++++++++++++++++++++++++++++++++ selection.ads | 16 +++++++++++++++ 9 files changed, 254 insertions(+) create mode 100644 bubble.adb create mode 100644 bubble.ads create mode 100644 gnomesort.hs create mode 100644 mergesort.hs create mode 100644 quick.adb create mode 100644 quick.ads create mode 100644 quicksort.hs create mode 100644 selection.adb create mode 100644 selection.ads 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; + -- cgit