7

リストが1回のパスで分割される効率的なバージョンのクイックソートを作成する方法を知りたい です。

私はこのコードの断片を持っています、

    let rec quicksort' = function
[] -> []
| x::xs -> let small = List.filter (fun y -> y < x ) xs
           and large = List.filter (fun y -> y > x ) xs

in quicksort' small @ (x :: quicksort' large);;

しかし、ここではリストを 1 回以上調べています (小規模と大規模で 2 回のクイックソートを呼び出しています)。

アイデアは、リストに何度もアクセスせずに、1 つのステップで実行することです。

4

2 に答える 2

20

List.partitionは次の方法です。

let rec quicksort = function
    | [] -> []
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs
               in quicksort smaller @ (x::quicksort larger)

List.partitionを介した1回の冗長なトラバーサルを回避するのに役立つことに注意してくださいxs。クイックソートが機能する方法であるため、小さい部分と大きい部分を再帰的に並べ替える必要があります。

quicksortこのバージョンのは効率的とは言えません。クイックソートアルゴリズムは、入力配列を再帰的に変更する固有のインプレースアルゴリズムです。もう1つの要素はピボットの選択です。ピボットとして最初の要素を選択することは、必ずしも良い考えではありません。

これらの要因により、効率の実装が大幅に異なります（おそらく使用Arrayと変更）。クイックソートオンListは、アルゴリズムのアイデアとその再帰の美しさを示すために使用する必要があります。

于 2012-05-15T11:06:44.967 に答える
4

効率的な並べ替え関数を作成する必要がある場合は、この洞察に満ちた論文を読むことをお勧めします:並べ替え関数のエンジニアリング。それ以外の場合は、List.sortもかなりよく書かれていると確信しています。

于 2012-05-18T20:46:24.570 に答える