Commits

Anonymous committed a5cf500

Added a set of Haskell examples of bubble sorting. This includes the "well known" solution, along with a slightly optimised version.

Comments (0)

Files changed (1)

01-BubbleSort/BubbleSort-Haskell/BubbleSort.hs

+import Data.List
+
+-- the list of integers to be sorted
+list :: [Int]
+list = [33,98,74,13,55,20,77,45,64,83]
+
+-- sample list of strings to be sorted
+list2 :: [String]
+list2 = ["foo","bar","baz","dooby","scooby","flooby","mooby","dooo"]
+
+-- the magic of the haskell bubblesort
+bubbleSort :: (Ord a) => [a] -> [a]
+bubbleSort [] = []
+bubbleSort xs =
+    iterate swapPass xs !! (length xs - 1)
+    where
+        swapPass [x] = [x]
+        swapPass (x:y:zs)
+            | x > y     = y : swapPass (x:zs)
+            | otherwise = x : swapPass (y:zs)
+
+-- the same as above, but we return a list of
+-- lists which contain the steps along the way
+bubbleSortProcess :: (Ord a) => [a] -> [[a]]
+bubbleSortProcess [] = []
+bubbleSortProcess xs =
+    take (length xs - 1 ) $ iterate swapPass xs
+    where
+        swapPass [x] = [x]
+        swapPass (x:y:zs)
+            | x > y     = y : swapPass (x:zs)
+            | otherwise = x : swapPass (y:zs)
+
+-- the magic of the haskell bubblesort, with a minor optimsation
+bubbleSortOpt :: (Ord a) => [a] -> [a]
+bubbleSortOpt [] = []
+bubbleSortOpt xs =
+    result !! (length result - 1)
+    where
+        result = unfoldr (\(l,b) -> if b then Just(l, lst l) else Nothing) (xs, True)
+        lst l = swapPass [] (l, False)
+        swapPass l ([x], b) = (l ++ [x], b)
+        swapPass l ((x:y:zs), b)
+            | x > y     = swapPass (l ++ [y]) ((x:zs), True)
+            | otherwise = swapPass (l ++ [x]) ((y:zs), b)
+
+-- the magic of the haskell bubblesort, with a minor optimsation
+-- AND the process along the way
+bubbleSortOptProcess :: (Ord a) => [a] -> [[a]]
+bubbleSortOptProcess [] = []
+bubbleSortOptProcess xs = unfoldr (\(l,b) -> if b then Just(l, lst l) else Nothing) (xs, True)
+    where
+        lst l = swapPass [] (l, False)
+        swapPass l ([x], b) = (l ++ [x], b)
+        swapPass l ((x:y:zs), b)
+            | x > y     = swapPass (l ++ [y]) ((x:zs), True)
+            | otherwise = swapPass (l ++ [x]) ((y:zs), b)
+
+
+-- program entry point
+main :: IO ()
+main =
+    do
+        putStr $ "Before: " ++ show list
+        putStr $ "\n After: " ++ show (bubbleSort list)
+        putStr $ "\n\nBefore: " ++ show list2
+        putStr $ "\n After: " ++ show (bubbleSort list2)
+        putStr $ "\n\nUnoptmised version sample process-----\n"
+        putStr $ concatMap ((++"\n").show) (bubbleSortProcess list)
+        putStr $ concatMap ((++"\n").show) (bubbleSortProcess list2)
+        putStr $ "\n\nOptmised version sample process-----\n"
+        putStr $ concatMap ((++"\n").show) (bubbleSortOptProcess list)
+        putStr $ concatMap ((++"\n").show) (bubbleSortOptProcess list2)