1

バブルソートに似ているが、いくつかの点で異なるソート方法を実装する方法を理解しようとしています。

擬似コードは次のようになります。

  1. リストを取得し、リストの最初の要素を取得します
  2. その隣の要素が小さい場合は、要素を交換します
  3. それ以外の場合、要素を移動済みとしてマークし、すべての要素がマークされるまで繰り返します

この問題の実装について私が考えた方法は次のとおりです。

sortElement [] elm= []
sortElement [x] elm= [x]
sortElement lis@(x:y:xs) elm = 
--first if is to find the element in the list that i want to move
if elm /=x  
then x:sortElement(y:xs) elm 
else if x > y then y:sortElement(x:xs) elm 
else lis

stackBubble lis = stackBubble' lis lis

stackBubble' [] [] = [] 
stackBubble' [x] [] = [x]
stackBubble' [] [x] = []
stackBubble' lis@(x:xs) lis1@(x1:xs1) = do 

sortElement(stackBubble' lis xs1) x1

私が得ているエラーは

関数 stackBubble の非網羅的なパターン

他の場所で提案したい場合：

sortElement(x:stackBubble' xs xs1) x1

次のようなものを取得したい場合、1回の反復後に完全にソートされたリストを取得します。

[4,2,7,1] => iterating 4 [2,4,7,1], after iterating all the elements [2,4,1,7].
4

3 に答える 3

2

私は修正版のコーディングを開始しましたが、そうしているうちに疑問が解決されました。デモンストレーションのために、とにかくここに含めます。

bubbleSort l =
  bSort l []
  where bSort []        acc = acc
        bSort [x]       acc = acc ++ [x]
        bSort (x:y:xys) acc
          | x > y     = bSort (acc ++ (y:x:xys)) []
          | otherwise = bSort (y:xys) (acc ++ [x])

これは、すべてのリストの連結のため、バブル ソートの基準から見ても、おそらく非常に非効率的であることに注意してください (アキュムレータ リストの先頭に追加し、必要に応じて逆にすることが最も望ましいでしょう)。この実装は非常にナイーブですが、合理的に簡潔で、おそらく有益です。ただし、肯定的な美徳よりも、その粗雑さのあからさまさのためです。

于 2012-06-12T02:35:50.447 に答える
2

stackBubble'一方の引数が空で、もう一方の引数に複数の要素がある場合、結果を指定しないため、エラーが発生します。

于 2012-06-12T01:59:04.433 に答える