0

list-basedクイックソートの私の実装は次のとおりです。

let partition pivot l = 
    let rec p left right = function
      | [] -> (left, right)
      | hd::tl ->
    let c = compare pivot hd
    in 
    if c > 0 then
      p (hd::left) right tl
    else 
      p left (hd::right) tl
    in
    p [] [] l;;

let quicksort l =
  let rec qs = function
    | [] -> []
    | pivot::tl ->
      let (left, right) = partition pivot tl
      in 
      (qs left) @ (pivot::(qs right))
  in 
  qs l;;

のリストで試してみると、100,000問題なく問題ありません。

ただし、 で試してみると1,000,000、 のエラーが発生しますstack_overflow。

stack_overflowスタックlog1000000 ~ 20サイズは

4

3 に答える 3

5

オペレーターは線形量の@スタックを使用すると思います。(これは、リストをクイックソートする際の問題の 1 つにすぎません。)

@Pervasives モジュールの の定義は次のとおりです。

let rec ( @ ) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

これは現状では非常に遅いソートです。これを本当に機能させたい場合は、もっと賢くする必要があります。少なくとも、末尾再帰バージョンの@.

于 2013-03-04T18:01:38.133 に答える
1

クイックソートは、リンクされたリストでは使用できません。うまくいきません。リストで使用する正しいソート アルゴリズムはマージ ソートです。基本的に、アルゴリズムでリスト連結を使用するとすぐに、それが正しく行われていないか、別のデータ構造を使用する必要があることに気付くはずです。リストには多くの利点がありますが、連結はその 1 つではありません。

于 2013-03-05T19:26:33.760 に答える
0

すでに述べたように、問題は @. これは解決できない問題ではありません。内部の並べ替え関数を、並べ替えと連結を行う関数として再定義する必要があります。

 let partition pivot l = 
     let rec p left right = function
       | [] -> (left, right)
       | hd::tl ->
     let c = compare pivot hd
     in 
     if c > 0 then
       p (hd::left) right tl
     else 
       p left (hd::right) tl
     in
     p [] [] l;;

 let quicksort l =
   let rec qs l acc = 
   match l with
     | [] -> acc
     | pivot::tl ->
       let (left, right) = partition pivot tl
       in 
       qs left (pivot::(qs right acc)) 
   in 
   qs l [];;
于 2013-03-15T06:05:13.360 に答える