1{-# LANGUAGE TypeFamilies #-} 2 3-- --------------------------------------------------------------------------- 4-- | 5-- Module : Data.Vector.Algorithms.Insertion 6-- Copyright : (c) 2008-2010 Dan Doel 7-- Maintainer : Dan Doel 8-- Stability : Experimental 9-- Portability : Portable 10-- 11-- A simple insertion sort. Though it's O(n^2), its iterative nature can be 12-- beneficial for small arrays. It is used to sort small segments of an array 13-- by some of the more heavy-duty, recursive algorithms. 14 15module Data.Vector.Algorithms.Insertion 16 ( sort 17 , sortBy 18 , sortByBounds 19 , sortByBounds' 20 , Comparison 21 ) where 22 23 24import Prelude hiding (read, length) 25 26import Control.Monad.Primitive 27 28import Data.Vector.Generic.Mutable 29 30import Data.Vector.Algorithms.Common (Comparison) 31 32import qualified Data.Vector.Algorithms.Optimal as O 33 34-- | Sorts an entire array using the default comparison for the type 35sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m () 36sort = sortBy compare 37{-# INLINABLE sort #-} 38 39-- | Sorts an entire array using a given comparison 40sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m () 41sortBy cmp a = sortByBounds cmp a 0 (length a) 42{-# INLINE sortBy #-} 43 44-- | Sorts the portion of an array delimited by [l,u) 45sortByBounds :: (PrimMonad m, MVector v e) 46 => Comparison e -> v (PrimState m) e -> Int -> Int -> m () 47sortByBounds cmp a l u 48 | len < 2 = return () 49 | len == 2 = O.sort2ByOffset cmp a l 50 | len == 3 = O.sort3ByOffset cmp a l 51 | len == 4 = O.sort4ByOffset cmp a l 52 | otherwise = O.sort4ByOffset cmp a l >> sortByBounds' cmp a l (l + 4) u 53 where 54 len = u - l 55{-# INLINE sortByBounds #-} 56 57-- | Sorts the portion of the array delimited by [l,u) under the assumption 58-- that [l,m) is already sorted. 59sortByBounds' :: (PrimMonad m, MVector v e) 60 => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m () 61sortByBounds' cmp a l m u = sort m 62 where 63 sort i 64 | i < u = do v <- unsafeRead a i 65 insert cmp a l v i 66 sort (i+1) 67 | otherwise = return () 68{-# INLINE sortByBounds' #-} 69 70-- Given a sorted array in [l,u), inserts val into its proper position, 71-- yielding a sorted [l,u] 72insert :: (PrimMonad m, MVector v e) 73 => Comparison e -> v (PrimState m) e -> Int -> e -> Int -> m () 74insert cmp a l = loop 75 where 76 loop val j 77 | j <= l = unsafeWrite a l val 78 | otherwise = do e <- unsafeRead a (j - 1) 79 case cmp val e of 80 LT -> unsafeWrite a j e >> loop val (j - 1) 81 _ -> unsafeWrite a j val 82{-# INLINE insert #-} 83