2

宿題のために SML でクイックソートを実装する必要があり、道に迷っています。以前はクイックソートの実装方法に慣れていなかったので、それについて読みましたが、読んだ実装はすべて命令型でした。これらはそれほど難しくないように見えますが、クイックソートを機能的に実装する方法がわかりませんでした。

ウィキペディアにはたまたま Standard ML (私の課題に必要な言語) のクイックソート コードがありますが、それがどのように機能するのかわかりません。

ウィキペディアのコード: 

val filt = List.filter
fun quicksort << xs = let
fun qs [] = []
 | qs [x] = [x]
 | qs (p::xs) = let
     val lessThanP = (fn x => << (x, p))
     in
       qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))
     end
in
  qs xs
end

特に、次の行がわかりません: qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs)). filt は、p* 未満の xs 内のすべてのリストを返します。これは p と連結され、>= p.* のすべてにコンスされます。

* << (x, p) 関数が x < p のときに true を返すと仮定します。もちろん、そうである必要はありません。

実際、これを入力すると、何が起こっているのかを少し理解するのに役立ちます。とにかく、私はその SML 関数を wiki のクイックソート疑似コードと比較しようとしています。

関数クイックソート（配列、「左」、「右」）

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

パーティションが次のように定義されている場所

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex' + 1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'

では、パーティショニングはどこで行われているのでしょうか。それとも、SML のクイックソートについて間違って考えているのでしょうか?

4

2 に答える 2

3

では、パーティショニングはどこで行われているのでしょうか。それとも、SML のクイックソートについて間違って考えているのでしょうか?

クイックソートの純粋に機能的な実装は、入力リストの構造的再帰によって機能します (IMO、これは言及する価値があります)。さらに、ご覧のように、"filt" を 2 回呼び出すことで、入力リストを 2 つのサブリスト (A と B など) に分割し、個別に処理することができます。ここで重要なのは、次のことです。

  • A のすべての要素がピボット要素以下 (コードの "p")
  • B のすべての要素がピボット要素より大きい

命令型の実装は、同じ配列内の要素を交換することにより、インプレースで機能します。あなたが提供した疑似コードでは、「パーティション」関数の事後不変は、入力配列の「左」から始まる（および「ピボットインデックス」で終わる）2つのサブ配列があることと、「ピボットインデックス」の直後から始まる別のものです。 ' そして 'right' で終わります。ここで重要なのは、2 つのサブ配列がサブリスト A と B の表現と見なされることです。

ここまでで、パーティショニングのステップがどこで行われるか (または逆に、命令と機能がどのように関連しているか) がわかったと思います。

于 2011-10-31T07:44:58.893 に答える
1

あなたはこう言いました：

filt は、p* 未満の xs 内のすべてのリストを返します。これは p と連結され、>= p.* のすべてにコンスされます。

それはあまり正確ではありません。 filtより小さい xs 内のすべてのリストを返しますpが、その新しいリストはすぐには と連結されませんp。qs実際、新しいリストは(再帰的に) に渡され、qs返されるものはすべて に連結されpます。

疑似コード バージョンでは、パーティショニングは変数のインプレースで行われarrayます。そのためswap、partitionループ内で表示されます。インプレースでパーティショニングを行うと、コピーを作成するよりもパフォーマンスが大幅に向上します。

于 2011-10-31T02:58:36.660 に答える