AIにできなくて人間にできることクラウドとは?VRとは?ブロックチェーンとは?マイニングとは?ノーコードNOCODEWebpia編集部Webpiaはプログラミングとノーコードについて紹介するWebメディアです。10~30代向けに記事を執筆しております。当サイトはページの一部でPR活動を実施し、得られた収益で運営されています。広告費用や収益性を考慮したランキング付けは、一切行なっておりません。詳細は、サイトポリシー、Webpiaでコンテンツが出来上がるまでを参照ください。こんにちは!今井(@ima_maru)です。今回は、ソーティングルゴリズムの一つ「マージソート」について、触れていきます。sort)とは?マージソートとは、「ソートアルゴリズム」の一種で、とても速いといわれている中の一つです。非常に安定しているソートで、考え方もわかりやすいです。平均するとクイックソートの速度には負けるけど、クイックソートよりも安定しているというソートです。ここではマージソートの主な考え方について書きます。マージソートの基本的な処理は、分割とマージに分かれます。最小単位まで分割してから考える「分割統治法」マージソートは、クイックソートと同じく「分割統治法」という手法を使ったソートアルゴリズムです。分割統治法とは、問題を細かく分け、それらすべての問題を解くことで、全体の問題を解いていくという手法です。分割統治法は、意外といろんな問題に応用が利きます!マージソートでは初めに、配列のデータ数が1個になるまで分割するという手法を取ります。当たり前ですが、配列のデータ数が1個なら、ソート済みの配列とみなすことができますよね。「1」もデータ数1の配列です(ソート済み)。したら次に、二つのソート済み配列を合体させて一つのソート済み配列をつくるということをします。実はこれが「マージ」と呼ばれる処理なのですが、ここでは説明をすっ飛ばします。「1」と「5」から「1,5」という配列を作ります。これで新しい配列のデータ数は2個となりました。次に、「1,5」と「2,8」から「1,2,5,8」という配列を作れば、これでデータ数は4個となります。次は、「1,2,5,8」と「3,4,6,7」から「1,2,3,4,5,6,7,8」という配列を作れば、これでデータ数は8個となります。こんな風に、まずはデータ数を1から始める。「マージ」という処理によって二つのソート済み配列を合体し、一つのソート済み配列を生成する。マージを繰り返すことでソート済み配列のデータ数を増やしていく。最終的に、元のデータと同じ大きさのソート済み配列が完成するというのがマージソートの流れになります。動画で見るととてもわかりやすいです。はじめは凸凹だった棒グラフが、徐々にサイズの大きな昇順のグループになっていく様子が見てわかります。最後は大きな二つのグループがマージされてソートが完了していますね。マージソートの速度の秘密は「マージ」にあるマージソートの速さのカギとなるのは、ソート名にも入っている「マージ」という処理です。「マージ」とは、二つのソート済みの配列を合体し、一つのソート済みの配列を生成する処理のことを言います。イメージは以下のような『スライム』の合体を想像してみてください。昇順ソート済みの「配列3」を生成する処理です。マージソートが速い理由は、この「マージ」という処理にひと工夫を加えているからです。その工夫は、それぞれの配列がすでに「ソート済み」ということを利用する点にあります。以下のような昇順ソート済みの配列Xと配列Yがあったとして、それらをマージした配列Zを作ることを考えます。どのようにすれば、配列Zを少ない処理数で作ることができるでしょうか?ここで、闇雲にソートの処理を書いていては、バブルソートや挿入ソートといった遅いソートと何も変わりません。マージソートでは、以下の性質を使います。配列Xの中で、一番小さい値は配列Xの先頭の値「1」。配列Yの中で、一番小さい値は配列Yの先頭の値「2」。配列Zの一番初めの場所に入る値は、「1」か「2」の二択ということになります。いうと、配列Zの一番初めに入るのは、配列Xと配列Y全体の一番小さい値であるからです。何が言いたいかというと、配列の2番目以降の値は、その配列の1番目の値以上だから候補から外れるよねってことです。比較対象は先頭の値のみでよいのです。これからわかることは、配列の先頭を比べながら小さい値のほうを配列Zに入れていけば良いということになります。実際にマージの流れを見てみましょう。この場合、「1<2」なので、配列Xの「1」が配列Zの1番目に入ります。次は、「3>2」なので、配列Yの「2」が配列Zの2番目に入ります。次は、「3<5」なので、配列Xの「3」が配列Zの3番目に入ります。次は、「4<5」なので、配列Xの「4」が配列Zの4番目に入ります。次は、「7>5」なので、配列Yの「5」が配列Zの4番目に入ります。このように比較を行っていけば、今回の例だと、最終的に配列Xの値がなくなり、配列Yの値のみが残ります。(以下のように)こうなれば、配列Yの値をそのまま配列Zの最後の部分に入れて終わりです。(今回は残った値が1つだけでしたが、複数残った場合も同様です。)なので、残った8を配列Zに入れてマージ完了です。このように、それぞれの配列がすでにソートされているということを利用して、残っている配列の要素の先頭を比較していくということを行っています。この工夫により、マージソートは無駄な比較が省けてとても効率の良いソート方法となっています。マージソートのアルゴリズム、どのように実現するか?わかりやすい動画を張っておきますので参考にしてみてください。降順(大きい値から小さい値)になるようにソート徐々にサイズが大きくなっていくことがイメージしやすい分割から併合(マージ)の流れがわかりやすい。マージソート以外の高速なソーティングアルゴリズム!最後に、ほかの高速なソーティングアルゴリズム、また、基本的なソーティングアルゴリズムの動画をご紹介して終わりにしたいと思います。ソーティングアルゴリズムの比較動画これはいろいろなソーティングアルゴリズムを紹介している動画です。左上にソート名が書いてあります。ソートするデータ数や速度設定が違うので注意してください。クイックソートについては以前に書いた記事があるので、興味がある方は是非ご覧ください。こんにちは!今井(@ima_maru)です。今回は、ソーティングルゴリズムの一つ「クイックソート」について、触れていきます。できるだけ簡単にわかりやすく解説していきた...以上「マージソートとは?図を使ってわかりやすく解説します!」でした!最後までご覧いただきありがとうございます。Webエンジニアになるために学ぶことを20個紹介!【新卒/学生向け】2022年6月19日GitHubとは何か?gitとの違いやメリットについてもわかりやすく解説!2022年6月18日プログラミングで作りたいものがない?これを見て!具体例・探し方を紹介!2022年5月25日なぜプログラミングは難しいのか?挫折率90%の原因と対策を教えます。(12)Webpia編集部Webpiaはプログラミングとノーコードについて紹介するWebメディアです。10~30代向けに記事を執筆しております。Webpia.MENUおすすめスクールスクールランキング副業エンジニア稼げない?もくじもくじTOP閉じるもくじ閉じる。