1

I am trying to implement bubble sort to sort my list by priority. For example, the list is of the following format with the 3rd element being priority:

  [("Ted", 100, 3), ("Boris", 100, 1), ("Sam", 100, 2)]

I have tried the standard bubble sort method below, however this did not work. Any suggestions would be appreciated. 

bubbleSort :: (Ord t) => [t] -> [t]
bubbleSort a = loop (length a) bubble a

bubble :: (Ord t) => [t] -> [t] 
bubble (a:b:c) | a < b = a : bubble (b:c)
           | otherwise = b : bubble (a:c)
bubble (a:[]) = [a] 
bubble [] = []

loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
loop num f x | num > 0 =  loop (num-1) f x'
         | otherwise = x
         where x' = f x
4

1 に答える 1

5

luqui が示唆しているようOrdに、並べ替えアルゴリズムの制約付きバージョンを直接実装するのではなく、カスタム比較を使用するより一般的なものを実装するのが通常です。

bubbleSortBy :: (t->t->Ordering) -> [t] -> [t]
bubbleSortBy cmp a = loop (length a) bubble a
 where
       bubble :: (Ord t) => [t] -> [t] 
       bubble (a:b:c) = case cmp a b of
                          LT -> a : bubble (b:c)
                          _  -> b : bubble (a:c)
       bubble l = l

loop :: Integral a    -- (Num, Ord) is a bit /too/ general here, though it works.
   => a -> (t -> t) -> t -> t
loop num f x | num > 0    = loop (num-1) f x'
             | otherwise  = x
         where x' = f x

バージョンは、Ord次のことから自明に続きます。

bubbleSort :: (Ord t) -> [t] -> [t]
bubbleSort = bubbleSortBy compare

しかし、多くの場合、あなたの場合のように、一般的なバージョンを直接使用する方が実用的です

import Data.Function(on)

sorted_priority3rd = bubbleSortBy ( compare `on` \(a,b,c) -> (c,a,b) )

これが行うことは、各比較の前に引数の順序を変更することです。明らかに、これによりバブルのソートがさらに遅くなります。通常、あなたはむしろそうします

import Data.List (sortBy)   -- this is a proper ( log ) sorting algorithm

sorted_by3rd = sortBy ( compare `on` \(a,b,c) -> c )

後で細かい順序を気にします。

于 2013-03-28T16:20:50.710 に答える