MLのクイックソート

Question

ケースの表現（クラスの次のセクションにあります）を使用せずに、私はクイックソートをやっていない理由を理解できません。それはどこかのループに入り、決して終わらない。

splitAtとappendは既に厳しくテストされていますが、ここではそれらのコードがあります。

fun append(xs, ys) = 
if null xs 
then ys 
else (hd xs) :: append(tl xs, ys) 

fun splitAt(xs : int list, x : int) = 
let 
    fun sp(ys : int list, more : int list, less : int list) = 
     if null ys 
     then (more, less) 
     else 
      if hd ys < x 
      then sp(tl ys, more, append(less, [hd ys])) 
      else sp(tl ys, append(more, [hd ys]), less) 
in 
    sp(xs, [], []) 
end 

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(xs, hd xs) 
    in 
     qsort(append(#2 s, #1 s)) 
    end 

そして、私は（のqsort（＃2秒）、のqsort（＃1 S））追加使用して同じ問題を取得しますが、私前者はそれだけで各ラウンドを持つ単一の再帰を必要とするため、より良いスタイルでしたが。 私は 'splitAt'はリストを2番目の引数よりも大きく、2番目の引数よりも小さく、そしてより小さい、そしてタプルを作成すると言うべきだと思います。 Appendは2つのリストを連結します。

PS：これは練習問題であり、テストや宿題ではありません。

Answer 1

ループのどこかに入り、決して終了しません。

再帰呼び出し時にサイズが縮小されないリストでqsortが呼び出される可能性があります。おそらくappend(qsort (#2 s), qsort (#1 s))に行ってください。しかし、それでも、#1 sと#2 sのそれぞれが常にサイズが小さくなることを確認できますか？

splitAtとappendはライブラリ機能ではないため、入力する必要があります。 @という組み込みの付属物と組み込みのList.partitionを使用してsplitAtを形成することを検討することもできます。

はinterwebs上のどこかに見つかったこの1に対する比較：

fun quicksort [] = [] 
    | quicksort (x::xs) = 
    let 
     val (left, right) = List.partition (fn y => y < x) xs 
    in 
     quicksort left @ [x] @ quicksort right 
    end 

Answer 2

これは宿題ではないので...

注意このことにより、[1,2]をソートするのでxs = [1,2]その後、splitAt(xs hd xs)戻り([1,2],[])かの試みということqsortのバージョンは... [1,2]を再度ソートします。それは決して終わらないでしょう。

代わりに、splitAtをxsのテールに適用することを提唱します。あなたのコードに最小限の微調整だけではappendとsplitAtを残すことなく、としてqsortの書き換えをされています

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(tl xs, hd xs) 
    in 
     append(qsort(#2 s), (hd xs) :: qsort(#1 s)) 
    end; 

そして、例えば、

- qsort [4,2,1,2,3,6,4,7]; 
val it = [1,2,2,3,4,4,6,7] : int list 

あなたが結果を追加し、その後二回qsortを適用することが重要です。追加の分割にqsortを一度適用しようとするとqsortを元のリストと同じサイズのリストにqsortを適用するまで減らそうとしています。

パターンマッチングが始まると、SMLは本当に楽しくなります。あなたは次の章を楽しむべきです。