[KMP77] を読んでみた - d.y.d.

17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート

[tsucchi1022]

おもしろい

[kenichiice]

「値に関するクイックソートの流れを逆向きから眺めてみると、 [元々値が存在した位置] を基準にマージソートした動きになっていることがわかりました。」

[ikajigoku]

クイックソートとマージソートの関係

[paulownia]

へえ

[Nagise]

クイックソートとマージソートにこんな関係があったとは…！

[hyuki]

"値に関するクイックソートの流れを逆向きから眺めてみると、 [元々値が存在した位置] を基準にマージソートした動きになっていることがわかりました。" ステキステキ！こういうの大好き！他のソートでもぜひ。

[smoking186]

逆から見る

[tarao]

クイックソートとマージソートの双対性っぽい話

[tumo300-500]

おもしろ

[yowa]

Knuth-Morris-Pratt の元論文。

[sucrose]

“[KMP77] を読んでみた”