[アルゴリズム] クイックソートの実装(Javascript編)

formula-ford-930921_1280
LINEで送る
Share on GREE
Share on LinkedIn

ソートアルゴリズムで最も高速といわれているクイックソートにチャレンジしてみます。
でもwikipediaの解説を見てみると、最も高速と言われながらも、データの並びや数によっては、必ずしも早いわけではないそうだ。
少し冷めてしまいそうなアルゴリズムだが、今までと何が違うかを考えながら仕様を確率してみたいと思う。

ソース

解説

サンプルソース作りが非常に難航しました。
それは、このアルゴリズムをちゃんと理解しておらず、
pivotをずっと分岐点だと勘違いしていたからです。
pivotは、あくまで数値の基準値であって、それのポジションは全く必要がなかったからですね。
さらに、wikipediaや他のサイトのソースコードでC++などの言語で書かれていたので、
それを元に移植してみたんですが、エラーに悩まされて、ようやく解決したという事でした。

mid関数

pivotを抽出する関数で、配列の先頭、中間、最終の数値を送って、3つの値の中間値を取得するようになってます。
これをもう少し簡略できれば、もう少しシンプルにかけたのだが、これを曖昧にすることで、ソート精度に影響がでるかどうかがわからないので、このまま続行しました。

関数内の禁則処理

quickSort関数の冒頭にある

などを書いておかないと、無限ループが発生してしまうので、少し慎重気味に書いておきました。

再帰処理

quickSort処理内でquickSort関数を実行することで、配列を次々と処理する再帰処理を実現してます。
サーバ内のフォルダ構成を表示する際などにもこのやり方をよく使いますが、初心者が慣れていないと無限ループしちゃうので、使い慣れましょうね。

参考リンク

クイックソート

解説
Javascript

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です


*