クイックソートを機能的言語で実装する

Question

私は宿題の割り当てのためにSMLでquicksortを実装する必要がありますが、私は迷っています。以前はクイックソートがどのように実装されているのかよくわかっていなかったので、私はそれを読んでいましたが、私が読んだすべての実装は不可欠でした。これらはあまりにも難しくはありませんが、クイックソートを機能的に実装する方法はわかりませんでした。

WikipediaはスタンダードML（割り当てに必要な言語）でクイックソートコードを使用していますが、どのように動作しているのかわかりません。

ウィキペディアコード：qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))：特に

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 

、私はこの行を理解していません。 filtはp>より小さいx *のすべてのリストを返します。これはp>にすべて連結されます。>

* <と仮定して<（x、p）関数はtrueを返します。 x < p。もちろん、そうである必要はありません。

実際、これを入力すると、何が起こっているのかを理解するのに役立ちます。とにかく、私はそのSML関数をwikiのquicksort擬似コードと比較しようとしています。パーティションが

だから

// 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' 

、正確にパーティショニングが起こっていると定義される

関数クイック（アレイ、 '左'、 '右'）

// 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') 

？あるいは、SMLのクイックソートについて間違って考えていますか？

Answer 1

ここで、パーティションはどこで起こっていますか？あるいは、SMLのクイックソートについて間違って考えていますか？

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

• Aのすべての要素がピボット要素（コード中の「P」）Bの
• すべての要素以下であるピボット要素より大きい

必須の実装は、同じ配列内の要素を交換することでインプレースで動作します。あなたが提供した擬似コードでは、 "パーティション"関数のポストインバリアントは、入力配列の '左'から始まり（ 'pivotIndex'で終わる）、 'pivotIndex'の直後の2つのサブ配列'と'右 'で終わる。ここで重要なのは、2つのサブアレイがサブリストAおよびBの表現であると見ることができることです。

私は今、パーティション分割のステップが起こっていると思っています（逆に、関係がある）。

Answer 2

あなたはこれを言った：

FILTは以下> = Pすべてに短所-EDであるPと連結されたp *、よりXS内のすべてのリストを返します*

。

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

擬似コードバージョンでは、パーティション分割がarray変数でインプレースで行われます。だから、partitionループにswapと表示されています。インプレースでパーティション化を行うと、コピーを作成するよりもパフォーマンスが向上します。