ソートの安定性・内部ソートかマージソートのメリットの1つに安定ソートである点があります。同じ値の順序関係を維持しながらソートを行うことができます。ソートに外部メモリ(作業用配列)を使う必要があるため、内部ソートとはなりません(外部ソートです)。シェルソートの仕組み挿入ソートは、昇順(降順)に近ければ近いほど早くソートできるアルゴリズムでした。シェルソートは、挿入ソートを改良したソート方法です。具体的には少しずつ「昇順(降順)」に近づけながらソートを行うアルゴリズムです。ある一定間隔に要素を取り出し、挿入ソートを行います。(下の図の間隔:4つごと)つぎに、間隔を詰めて要素を取り出し、挿入ソートを行います。(下の図の間隔:2つごと)間隔が1になるまで繰り返し挿入ソートを行います。間隔が1のとき(つまり普通の挿入ソートと同じ)にソートを行うことでソートが完了します。下のように書くことができます。初期値をデータ数の半分とし、徐々に間隔を半分にしていきましたね。121......」を大きい順に*2適用させています。9)を超えない最も大きな値に設定することでより早くシェルソートを行うことができます。下のように書くことができます。シェルソートの正しい計算量は未だに未解決となっています。減らすことができます。安定性・内部ソートかシェルソートは挿入ソートとは異なり、隣り合ったデータ以外でデータを交換しまくるため、同じ値の順序関係が崩れてしまうことがあり、安定ソートとはいえません。シェルソートは外部メモリ(作業用配列)を使わずにソートできるため、内部ソートです。ヒープソートの仕組みヒープソートは、データを「順序木*3」と呼ばれる木構造に構成し、最大値(最小値)を取り出して整列済みにしていくことでソートを行うアルゴリズムです。データを木構造にし、順序木(ヒープ)にします。すると、木構造の根が一番大きい値となるので先頭と未確定列の最後尾を交換し、データ「5」の位置が確定します。確定したら再び順序木をつくります。これをすべてのデータが確定するまで繰り返します。ヒープソートの詳しいアルゴリズムなどヒープソートについては、こちらの記事に詳しい内容が書いてあるので興味がある方はぜひご覧ください!www.momoyama-usagi.com5.応用4ソートのまとめでは、今回説明した4つのソートを簡単にですがまとめていきましょう。基本3ソートの特徴クイックソート:基準値以上のデータと基準値以下のデータの2つにわけるのを再帰的に繰り返すことでソートしていく。分割統治法を用いたソート方法。マージソート:配列を2分割ずつしていき、分割したデータをマージしていくことでソートを行う。分割統治法を用いたソート方法。シェルソート:一定間隔おきにデータを取り出したものをソートしていき、徐々に取り出す間隔を狭めながらソートしていく。ヒープソート:未整列のデータを順序木にし、木構造の根からデータを取り出し、整列済にするのを未整列のデータがなくなるまで繰り返してソートを行う。Yes※1:安定性は、同じ値のデータをソートしたときに順序関係が保存されるかどうかを表す。※2:内部(ソート)は、ソートの際に外部メモリ(作業用配列など)が不要かどうかを表す。6.練習問題では、基本情報や応用情報の問題で何問か練習してみましょう。今回は応用情報の問題が多めです。練習1整列アルゴリズムの一つであるクイックソートの記述として、適切なものはどれか。午前問7]ア:対象集合から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで、整列を行う。イ:対象集合から最も小さい要素を順次取り出して、整列を行う。ウ:対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つよう挿入して、整列を行う。エ:隣り合う要素を比較し、逆順であれば交換して、整列を行う。練習2分割統治法を適用した整列(ソート)アルゴリズムはどれか。午前問12]ア:クイックソートイ:選択ソートウ:挿入ソートエ:ヒープソート練習3データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで、図中のデータ列中の縦の区切り線は、その左右でデータ列が分割されていることを示す。午前問6]ア:クイックソートイ:シェルソートウ:ヒープソートエ:マージソート練習4次の手順はシェルソートによる整列を示している。6を手順1~4に従って整列するとき、手順(3)を何回繰り返して完了するか。]は小数点以下を切り捨てた結果を表す。データ列を、互いにH要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、挿入法を用いて整列する。Hが0であればデータ列の整列は完了し、0でなければ(2)に戻る。クイックソートの説明です。イ:選択ソート(基本3ソート)の説明です。ウ:挿入ソート(基本3ソート)の説明です。エ:バブルソート(基本3ソート)の説明です。解答2解答:ア分割統治法とは、そのまま解くのが難しい問題を、いくつかの小さくて簡単な問題にして解き、最後にもとの問題にまとめることで問題を解いていく方法です。選択肢の4つの中で、分割統治法を用いているソート法はクイックソートなので、答えはアとなります。細かくしていくことでソートしていく分割統治法を用いたアルゴリズムです。)解答3解答:エ各データの隣り合う同士でソートされてそれぞれ要素数2のグループとなり、要素数2のグループ同士でソートされ要素数4に......、となるソートはマージソートである。★各選択肢の解説★ア:クイックソートであればある基準値を基準にデータを分ける操作があるはずだがそんな操作はない。イ:シェルソートであれば一定間隔ごとの部分列ごとにソートされるはずだがそんな操作はない。ウ:後ろから(前から)ソートされるが、そんな気配はないのでこれもダメ。解答4解答:アこの問題で大切なのは、データの中身よりも要素数である。そのため、データの中身は一切関係がない。今回は、要素数が9のデータをシェルソートする。そのため、最初のHは3、1回目操作3でHは1、2回目の走査3でHは0となるので答えはアの「2」となる。8.さいごに今回は前回の基本3ソートアルゴリズムに引き続き、4つの応用ソートアルゴリズムについてまとめていきました。応用ソートアルゴリズムはプログラムこそ書ける必要はありませんが、少なくとも仕組みは頭にいれておきましょう。今回でアルゴリズム関連の記事は一旦中断したいと思います。今まで見ていただきありがとうございました!*1:ここで再帰関数を使います。再帰関数ってなんだっけとなった人はこちらの記事で確認することをおすすめします。成立する木構造のことを表します。順序木のことをヒープと呼ぶこともあります。システムオートマトンPrologCLOSEサイト内検索を行います。はてなブログPro数学と情報が得意な大学生です。累計:リアルタイム現在の閲覧者数:。