Haskell Bubble排序在三部分Tuple

我想實現氣泡排序按優先級排序我的列表。例如，該列表是第三元素是優先級的格式如下：Haskell Bubble排序在三部分Tuple

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

我已經試過低於標準冒泡排序的方法，但是這並不工作。任何建議，將不勝感激。

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

來源

2013-03-28 user2214957

你的函數對整個元組進行排序，所以如果你想對元組的第三個元素進行排序，你需要修改一些東西。順便說一句，不要使用冒泡排序。 – augustss

@augustss我可以在泡泡排序中使用什麼？插入排序？爲什麼我不應該使用冒泡排序？ – user2214957

這只是冒泡排序非常低效。 – leftaroundabout

作爲暗示由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-28 16:20:50 leftaroundabout

謝謝你。如果列表元素被切換以便優先級處於第一位，那麼上面的問題中的基本代碼應該是正確的？該排序將在它找到的第一個項目上運行。 – user2214957

它將在Ord實例定義的任何操作上運行。在3元組的情況下，這恰好是：第一個元素的優先級，然後是第二個，然後是第三個，然後是「EQ」。 – leftaroundabout

Haskell Bubble排序在三部分Tuple

回答

相關問題