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

回答

相关问题