[記事公開日]2014/12/11
[最終更新日]2016/11/26

基本情報技術者試験 2-6(整列)

 

 

データを並べ替える方法にはいくつかあります。

 

①基本交換法(バブルソート)

②基本選択法

③基本挿入法

④シェルソート

⑤クイックソート

⑥ヒープソート

 

①基本交換法(バブルソート)

⇒隣同士と比較し、交換する。

 

例えば「1234」を「1234」にしたいとき、

「1234」

「1234」

「1234

と比較し、交換していきます。

 

●基本交換法の交換回数

⇒バラバラ。初期値によって変わる。上の例では2回でした。

 

 

●基本交換法の比較回数

⇒n(n-1)/2回

「n」というのはデータの数のことです。上の例では、nは「5」ですから、「5(5-1)÷2=10回」です。交換は2回しかしていませんが、比較は10回しています。

 

★「比較回数」なのか、「交換回数」なのかは区別しておいてください。

 

<例>

初期:54312

1回目:5-4(→45312)

2回目:5-3(43512)

3回目:5-1(43152)

4回目:5-2(43125)

(4回)

 

・比較の順序

先頭からスタートします。右隣と比較して、大きな値の方を右へスライドさせていきます。この時点(4回目)で一番大きな値は「5」だということが分かりました。次からは、この「5」は「一番大きな値」と分かったため、比較の対象としなくてよいです。「大きな値」が右にいくこともあれば、「小さな値」が右にいくこともあります。どちらの場合でも、「基本交換法」です。

 

5回目:4-3(34125)

6回目:4-1(31425)

7回目:4-2(31245)

(3回)

 

8回目:3-1(13245)

9回目:3-2(12345)

(2回)

 

10回目:1-2(そのまま)

(1回)

 

合計10回です。

 

●基本選択法(選択ソート)

⇒最大値(または最小値)を端に置く。

 

初期:4132
・4と1を比較。(1を最小値として認識しておく)

・1と3を比較。(1を最小値として認識しておく)

・1と2を比較。(1を最小値として認識した)

(3回)

「1」が最小値と分かったので、左端へ追いやってしまいます。

(4132→1432)

 

先頭の「1」はもう比較対象にしません。

 

次に、左から2桁目に「1」の次に大きな値を置きます。

 

1432」

4と3を比較。(3を最小値として認識しておく)
3と2を比較。(2を最小値として認識した)

(2回)

14321243)

 

4と3を比較。(3を最小値として認識した)

(1回)

 

(12431234)

 

4ケタの場合、比較回数は「6回」です。

 

●基本選択法の交換回数

⇒最大で、「n-1回」。

 

<例>54321 : 4回

54321→15432→12543→12354→12345

 

<例>12345 : 0回

12345

 

●基本選択法の比較回数

⇒n(n-1)/2回

 

●基本挿入法(挿入ソート)

先頭から順に”整列済み”とみなしていきます。あの整列済みの中に挿入をしていきます。

 

<例>

初期:41325

まず先頭の「4」を整列済みとします。

 

 

次に、1番目「4」と2番目「1」を比較し、必要であれば2番目を正しい位置へ挿入します。

41325→14325

 

次に、2番目「4」と3番目「3」を比較し、必要であれば3番目を正しい位置へ挿入します。

14325→13425

 

※この時点では、「134」までが「整列済み」となる。

 

次に、3番目「4」と4番目「3」を比較し、必要であれば3番目を正しい位置へ挿入します。

13425→12345

 

次に、4番目「4」と5番目「5」を比較し、必要であれば3番目を正しい位置へ挿入します。

12345→12345(挿入なし)

 

 

挿入ソートは、値がぶっ飛ぶという特徴があります。隣同士で交換される必要はありません。また、挿入をしていくという点では、「基本交換法=バブルソート」や「基本選択法=選択ソート」に比べて高速になります。

 

 

●シェルソート

「543 162 897」

3つおきに並べる

(518)(469)(327)

その中で順番にする

(158)(469)(237)

2つおきに並べる

(18627)(5493)

その中で順番にする

(12678)(3459)

1つおきに並べる

126783459

その中で順番にする

123456789
(終わり)

 

●クイックソート

基準より上か、下か。一番早い方法!!
「85431629」

適当に真ん中らへんの3を基準にする。

3より下のグループ(12)と、基準3と、3より大きいグループ(45689)ができる。

(そのグループの中でまた基準を作り、残り2個になるまで細分化していく。)

(12)は残り2個になり、比較が終了。

(45689)は6を基準に(45)(6)(89)ができる。
残り2個の中も順番を買える必要はなさそう。

12345689
(終わり)

 

●ヒープソート

木の3パターン
「54213」