Skip to content

Instantly share code, notes, and snippets.

@oboje
Forked from jason2506/sorting.hs
Created November 29, 2017 14:14
Show Gist options
  • Save oboje/16db012cac2377fbe1b4f378317d5c1d to your computer and use it in GitHub Desktop.
Save oboje/16db012cac2377fbe1b4f378317d5c1d to your computer and use it in GitHub Desktop.
[Haskell Practice] some common sorting algorithms
import Data.List
bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort [] = []
bubbleSort (first:[]) = first:[]
bubbleSort (first:remains) =
if first < smallest
then first:(bubbleSort bubbledRemains)
else smallest:(bubbleSort (first:(tail bubbledRemains)))
where bubbledRemains = bubbleSort remains
smallest = head bubbledRemains
insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (first:remains) = before ++ [first] ++ after
where (before, after) = span (< first) $ insertionSort remains
selectionSort :: (Ord a) => [a] -> [a]
selectionSort [] = []
selectionSort list = first:(selectionSort remains)
where (first, remains) = fetchSmallest list
fetchSmallest (first:[]) = (first, [])
fetchSmallest (first:remains) =
if first < smallest
then (first, smallest:others)
else (smallest, first:others)
where (smallest, others) = fetchSmallest remains
mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort (first:[]) = first:[]
mergeSort list = merge (mergeSort front) (mergeSort back)
where (front, back) = splitAt ((length list) `div` 2) list
merge list [] = list
merge [] list = list
merge list1 list2 =
if first1 < first2
then first1:(merge (tail list1) list2)
else first2:(merge list1 (tail list2))
where first1 = head list1
first2 = head list2
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (first:remains) = (quickSort before) ++ [first] ++ (quickSort after)
where (before, after) = partition (< first) remains
main = do
putStr $ show $ bubbleSort [18, 25, 29, -32, 9, 17]
putStr "\n"
putStr $ show $ insertionSort [18, 25, 29, -32, 9, 17]
putStr "\n"
putStr $ show $ selectionSort [18, 25, 29, -32, 9, 17]
putStr "\n"
putStr $ show $ mergeSort [18, 25, 29, -32, 9, 17]
putStr "\n"
putStr $ show $ quickSort [18, 25, 29, -32, 9, 17]
putStr "\n"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment