diff options
Diffstat (limited to 'sort/pancakesort.hs')
-rw-r--r-- | sort/pancakesort.hs | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/sort/pancakesort.hs b/sort/pancakesort.hs new file mode 100644 index 0000000..30993ba --- /dev/null +++ b/sort/pancakesort.hs @@ -0,0 +1,30 @@ + + + +pancakeSort :: Ord a => [a] -> [a] +pancakeSort [] = [] +pancakeSort cakeStack = + let selectedCake = indexOfLargest cakeStack + cakeStack' = (doFlip (length cakeStack)) . (doFlip selectedCake) $ cakeStack + in (pancakeSort (init cakeStack')) ++ [last cakeStack'] + + + +indexOfLargest :: Ord a => [a] -> Int +indexOfLargest (x:xs) = + let f m i j y = if length y == 0 + then i + else if (head y) > m + then f (head y) j (j+1) (tail y) + else f m i (j+1) (tail y) + in f x 0 1 xs + + + +doFlip :: Int -> [a] -> [a] +doFlip depth list = + let prefix = take (depth + 1) list + rest = drop (depth + 1) list + in (reverse prefix) ++ rest + + |