6分SHAREツイートシェアはてブLINEPocket今井こんにちは!今井(@ima_maru)です。今回は、ソーティングルゴリズムの一つ「クイックソート」について、触れていきます。Hoareさんが考案した「ソーティングアルゴリズム」の一種で、内部ソートの中では最も速いといわれているアルゴリズムです。今井とりあえず、一番速いソート方法って覚えてください!もちろん、それ以外にも同じぐらい速いソーティング方法はあり、条件や最悪の場合などを考えればクイックソートより速くなることあります。この記事の終わりに、ほかの高速なソーティングアルゴリズムの紹介やクイックソートとの比較などを書きますので是非ご覧ください。↓ソートとは何ぞやって方へ!↓ソート?ソーティング?ってなんのことニャ?ぷーにゃん今井ソートとは、本をタイトル順に並べることだったり、生徒を身長順に並べることだったり、順序のつけられるものを順序通りに並べなおす行為のことだよ。優先度をつけてそれ通りにタスクを実行したいとき、ありますよね。以下のようなタスクがこのように並んでいたらどうでしょうか?(優先度70)一週間後のテストの勉強をする。(優先度50)二週間後までの課題を終わらせる。(優先度20)旅行の計画を立てる。この順に並んでいるならば上から処理していけば大丈夫ですね。「課題が二週間後までではなく、今日までだった!」と気づいたらどうでしょう。(優先度70)一週間後のテストの勉強をする。(優先度99)「今日の24:00締め切り」の課題を終わらせる。(優先度20)旅行の計画を立てる。優先度が99に上がり、優先度順ではなくなってしまいました。ここでソートが必要になります。(優先度99)「今日の24:00締め切り」の課題を終わらせる。(優先度70)一週間後のテストの勉強をする。(優先度20)旅行の計画を立てる。こんな風にソートを行い、上から優先度順に並ぶように整列します。プログラミングしていく上で、データが数字順に並んでいたほうがいいことはたくさんあります。そんな時、このソート、すなわち、順番どおりに並べるということが必要になります。今回の例に挙げたような3個ぐらいのデータでは何も問題ないですが、1万、10万というデータ数を扱うことを考えるとどうでしょうか?効率よくソートする方法を知らなければ、とっても遅いプログラムになってしまいます。そこで登場するのが効率の良いソートの一つが、今回の主役「クイックソート」なんです。そのままでは解くことの難しい大きな問題を、小さな問題に分割して考えるという手法です。分割統治法とは、大きな問題を小さな問題の集合ととらえて、その小さな問題をすべて解くことで元の大きな問題の答えを得ようとする手法です。トランプを買った時の順番に並べなおすとき、皆さんならどうしますか?私だったら以下のようにします。♦ダイヤ」別に分けるマークそれぞれの13枚(A~K)を並び替えて最後に合わせる皆さんもこうするのではないでしょうか?どうして、その4つのマーク別に分類するのか?これは、単純な理由で「枚数が少ないほうが並べなおしやすいから」です。このように52枚のカードをそのまま並び替えるのではなく、「一度4つのマーク別に分割してから、それぞれを並び替えて最後にくっつける」という手法をとるのが分割統治法の考え方です。今回のクイックソートは、基準値をとることで元のデータを分割していきます。クイックソートは実際何を行っているのか?ここではクイックソートの実際の処理ではなく主な考え方について書きます。(実際の処理は下で解説)先ほども書きました通り、クイックソートは、元のデータを分割していく分割統治法という手法を用います。クイックソートは、データを分割する際に、基準より大きい値と小さい値という条件で2分割します。実はこの「基準より大きい値と小さい値」という条件がクイックソートの「核」となる部分です。説明のために0~19までの数字をランダムに並べ替えたものを用意します。19とソートしたいと思います。基準値(ピボット)を決める必要があります。今回は左端の「10」を基準値としてみましょう。基準値を決めたら、基準値より小さい値と基準値より大きい値で場合分けしていきます。左に小さい値、右に大きい値を置いていきましょう。したら、「0~9」は左のグループに入り、「11~19」は右のグループに入ります。基準となった「10」は右のグループに入れておきましょう。ここまでの結果、新しい2つのグループ「x<10のグループ」「10≦xのグループ」に分割できました。「左のグループのどの値も、右のグループのどの値よりも小さい」ということがわかると思います。1(左)と19(右)を比べても、9(左)と10(右)を比べても、絶対に右のグループのデータのほうが大きい値なんです。言ってることは単純で、「基準の値より小さい値と大きい値」に分けているから、右のグループのほうが絶対に大きいねってことです。このことがわかると、左のグループと右のグループをそれぞれソートしてくっつければ順番どおりになることがわかるのです。先ほどのトランプの例と同じです。今の分割を先ほどの左のグループについてもう一回行いましょう。右のグループの値」という関係が成り立っていることに注意しましょう。このグループとは別に、10以上のグループにもこの操作を行いましょう。すると、どうやらまた新しい2グループに分割できることがわかります。これが、分割統治法の考え方「小さな問題に分割して考える」ということです。今までの流れをまとめて、クイックソートの流れ図を書いてみましょう。このように基準値をもとに分割するというのが、クイックソートの主な流れです。「基準値(ピボット)と比較して小さい値と大きい値に分ける」という処理を、分割されたグループそれぞれについて繰り返し行っていくというソーティングアルゴリズムということもできます。すると最終的にすべてグループに属するデータが1個になり、その状態こそソートされた状態なのです。最終的に、データ数が2つや3つになりますが、その際の処理は少しイメージしにくいかもしれません。実際の処理は次で書きます。「"100%流れが来ている職業"に、ほぼ"100%転職できる"としたら、あなたは悩みますか?それとも今すぐ行動しますか?」なおホリエモンも認めたプログラミングスクールで稼げる人材になろう!\稼げる人材になることに特化!/"転職成功率99%"のTECH::EXPERTはこちら※14日間の全額返金保証付きクイックソートのアルゴリズム、どのように実現するか?実際の処理方法は動画で理解した後、それと照らし合わせながらソースコードを見るのが効率的だと思います。わかりやすい動画を張っておきますので参考にしてみてください。クイックソートのわかりやすい解説動画MEMO真ん中の値を基準値に取っている基準値の取り方次第で効率が良くない場合があるMEMO降順(大きい値から小さい値)になるようにソート中規模のソート(4:25~)バブルソート、シェーカーソートとの比較(5:03~)C言語/C++で書くクイックソート初めに言っておきますが、こんな長いクイックソートのコードを書くより、内容的にも労力的にも、用意されているライブラリの関数を使うのがいいです。アルゴリズムの勉強ということにお使いくださいませ。C++をベースに書いています。right);}クイックソート以外の高速なソーティングアルゴリズム!最後に、ほかの高速なソーティングアルゴリズム、また、基本的なソーティングアルゴリズムの動画をご紹介して終わりにしたいと思います。ソーティングアルゴリズムの比較動画これはいろいろなソーティングアルゴリズムを紹介している動画です。左上にソート名が書いてあります。ソートするデータ数や速度設定が違うので注意してください。どちらも、とても高速なソーティングアルゴリズムとして有名です。今後紹介していけたらと思います。週1でブログ書いてます。