Skip to content

Instantly share code, notes, and snippets.

@dmalikov
Created June 11, 2012 18:22
Show Gist options
  • Save dmalikov/2911744 to your computer and use it in GitHub Desktop.
Save dmalikov/2911744 to your computer and use it in GitHub Desktop.
Algorithms: design and analysis I, exercise1 (week1)
{-# LANGUAGE UnicodeSyntax #-}
import Control.Applicative ((<$>))
import Inversions
inputFile ∷ FilePath
inputFile = "IntegerArray.txt"
main ∷ IO ()
main = print =<< inversions <$> map (read ∷ String → Int) <$> lines <$> readFile inputFile
{-# LANGUAGE UnicodeSyntax #-}
module Inversions (inversions) where
inversions ∷ Ord α ⇒ [α] → Int
inversions = fst . inversions'
where
inversions' list@(_:_:_) = (leftInvs + rightInvs + splitInvs, sortedList)
where (leftInvs, leftSortedList) = inversions' leftList
(rightInvs, rightSortedList) = inversions' rightList
(splitInvs, sortedList) = mergeInvs leftSortedList rightSortedList
(leftList,rightList) = splitAt ((`div` 2) $ length list) list
inversions' list = (0, list)
mergeInvs ∷ Ord α ⇒ [α] → [α] → (Int,[α])
mergeInvs = mergeInvs' 0
where mergeInvs' i a [] = (i, a)
mergeInvs' i [] a = (i, a)
mergeInvs' i (x:xs) ylist@(y:_) | x < y = (i + invs, x : invList)
where (invs, invList) = mergeInvs' 0 xs ylist
mergeInvs' i xlist (y:ys) = (i + invs + length xlist, y : invList)
where (invs, invList) = mergeInvs' 0 xlist ys
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment