FC2ブログ

アルゴリズム【スマート記述クイックソート】

さて、みなさんおなじみのクイックソート。
値を交換するときに空白の変数を使用しない方法と、
二分木のノード(点)にきたとき再帰コールを使ったやつです。

quicksort.png

ピボットという中央値は使ってないです。
メジアン探すのに、交換だけじゃなくてループも探すし
改良して、メジアン決めるのもいいかも

簡単のため、2分割していやす

まぁ、奇数個ある列に対しては並び替えた後の配列の
おしりから、比較しながら、右シフト代入してるんですけどね!


さて、aとbを入れ替えるとき、

a=a+b
b=a-b
a=a-b

と記述するだけで入れ替えることができます。


a=3,b=7
としたときの様子を見てみましょう

①a=a+bによって、a=10,b=7となります。
②b=a-bによって、a=10,b=3となります。
③a=a-bによって、a=7,b=3となります。

順番に解釈、実行されることを利用した交換法ですな


ピボットを使った改良版は下のとおりです。

quick_kai.png

ふぅ・・・。
時系列のランダムでピボット選んで、並び替えをして
分岐処理します。

以外に、難しかったけどね。

スマートかどうかは、ちょっと首を傾げるかもしれませんね^^;
スポンサーサイト



テーマ : 日記・日誌
ジャンル : コンピュータ

コメントの投稿

非公開コメント

ぶろぐかんりしゃ

SmartWoods
最近MoEは・・・
一休み

***** ひとこと *****

MoEの後継ともいわれる
Resonance gamez
完全スキルMMOが
気になるところ



********************


↓2016/3/26更新
My MoE









**********

NEWとらっくばっく
あーかいぶ
かてごりー
リンク
ぶろぐないけんさく
RSSふぃーど
おともだちになろ

この人とブロともになる