マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
2023-12-13 更新
基本情報技術者試験は、2023年4月から新制度で実施されています。
この連載では、新制度の擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。
今回は、「 マージソート 」というアルゴリズムを取り上げます。
マージソートの基本的な手順
はじめに、マージソートの基本的な手順を説明します。
マージソートのマージ（merge）は、「結合する」という意味です。
マージソートは、2つのソート済みの配列を結合して、ソートされた1つの配列にします。
例として、図1を見てください。
昇順にソートされた配列Aと配列Bがあります。
これらを結合して、昇順にソートされた1つの配列Cにしてみましょう。
配列Aと配列Bは、昇順にソートされているのですから、それぞれの先頭の要素を比較して小さい方を取り出し、それを配列Cに格納することを繰り返せば、昇順にソートされた1つの配列になります。この手順を繰り返すと、配列Aの要素が先に無くなるので、配列Bに残った要素は、そのまま取り出して配列Cに格納します。
図2にマージソートが完了するまでの手順を示します。
図2 マージソートが完了するまでの手順
1つの配列をマージソートする方法
マージソートは、2つのソート済みの配列を結合することでソートしますが、1つの配列をソートすることもできます。そのためには、結合の前に分割の処理を行います。
例として、図3を見てください。
ソート前の配列には要素数が4個ありますが、これを要素数1個の4つの配列になるまで分解すれば、ソート済みの配列が4つになります（要素数が1個の配列は、ソートされているとみなせます）。
ソート済みの4つの配列を2つずつ結合すると、ソートされた2つの配列になります。
さらに、ソート済みの2つの配列を結合すると、ソートされた1つの配列になります。
マージソートのプログラムの例
マージソートのプログラムの例を示しましょう。
リスト1は、旧制度の平成22年度春期試験の問8に示された「マージソート」のプログラムを、現行制度の擬似言語の記述形式にしたものです。
リスト1 マージソートのプログラムの例（出典：H22春問8改）code
// 手続Sortの定義（ここから）
〇Sort(整数型の配列：list, 整数型：num)
整数型の配列：slist1, slist2
整数型：i, num1, num2
// 配列listの要素数が1より大きいなら（分割可能なら）処理を行う
if (num ＞ 1)
// 配列listを配列slist1と配列slist2に分割する
num1 ← num ÷ 2
num2 ← num － num1
for (iを0から、i ＜ num1である限り、1ずつ増やす)
slist1[i] ← list[i]
endfor
for (iを0から、i ＜ num2である限り、1ずつ増やす)
slist1[i] ← list[num1 ＋ i]
endfor
// 分割した前側の配列list1を手続Sortの再帰呼び出しで分割する
Sort(slist1, num1)
// 分割した後側の配列list2を手続Sortの再帰呼び出しで分割する
Sort(slist2, num2)
// 手続Mergeでlist1とlist2を結合してlist1に格納する
Merge(slist1, num1, slist2, num2, list)
endif
// 手続Sortの定義（ここまで）
// 手続Mergeの定義（ここから）
○Merge(整数型の配列slist1, 整数型：num1,
整数型の配列slist2, 整数型：num2,
整数型の配列：list)
整数型：i, j
i ← 0
j ← 0
// 配列slist1と配列slist2の先頭の要素を比較して小さい方を取り出し、
// それを配列listに格納することを繰り返す
while ((i ＜ num1) and (j ＜ num2))
if (slist1[i] ＜ slist2[j])
list[i + j] ← slist1[i]
i ← i ＋ 1
else
list[i + j] ← slist2[j]
j ← ｊ ＋ 1
endif
endwhile
// 配列slist1に要素が残っていたら、要素を取り出して配列listに格納する
while (i ＜ num1)
list[i + num2] ← slist1[i]
i ← i ＋ 1
endwhile
// 配列slist2に要素が残っていたら、要素を取り出して配列listに格納する
while (j ＜ num2)
list[j + num1] ← slist2[j]
j ← j ＋ 1
endwhile
// 手続Mergeの定義（ここまで）
手続Sortは、配列をマージソートします。
引数listにソートする配列を指定し、引数numに配列の要素数を指定します。
手続Mergeは、2つの配列を結合します。
引数slist1、num1、slist2、num2に結合する2つの配列とそれぞれの要素数を指定し、引数listに結合した要素を格納する配列を指定します。
ここでは、配列の大きさが省略されていますが、必要な領域が確保されているとします。
配列の要素番号は、0から始まるとします。
手続Sortの処理の中で、手続Mergeを呼び出しています。
手続Sortの処理の中で、手続Sortを呼び出している部分もあります。
これは、再帰呼び出し（関数や手続の処理の中で、同じ関数や手続を呼び出すことで繰り返しを実現する技法）です。
マージソートの分割や結合の繰り返しは、whileやforを使った表現で記述することが困難なのですが、再帰呼び出しで記述すれば容易です。
リスト1は、大雑把に説明すると以下のような手順です。
- 手続Sortで配列listを配列slist1と配列slist2に分割する
- 分割した前側の配列list1を手続Sortで分割する（再帰呼び出し）
- 分割した後側の配列list2を手続Sortで分割する（再帰呼び出し）
- 手続Mergeでlist1とlist2を結合してlist1に格納する
「こんな手順で上手く行くのだろうか？」と疑問に思うかも知れませんが、上手く行ってしまうのが、再帰呼び出しの便利で面白いところです。
マージソートのプログラムのトレースにチャレンジ
最後に、先ほどリスト1に示したプログラムのトレースにチャレンジしてみましょう（実際の試験問題にも、プログラムのトレースに関する設問がありました）。
トレースすれば、「こんな手順で上手く行くのだろうか？」という疑問が晴れるはずです。
ここでは、引数listに{3, 8, 2, 7, 5, 1}を、引数numに6を指定して、手続Sortを呼び出したとします。
図4にトレースの結果を示しますので、リスト1の内容と照らし合わせてください。
分割は、配列の前側、前側と進んで、前側の分割が終わったら、後側の分割に進みます。
前側と後側の要素が1つになったら結合が行われます。
マージソートのプログラムのトレースの結果
（2）{3, 8, 2}が、{3}と{8, 2}に分割される。
（3）{8, 2}が、{8}と{2}に分割される。
（4）{8}と{2}が、{2, 8}に結合される。
（5）{3}と{2, 8}が、{2, 3, 8}に結合される。
（6）{7, 5, 1}が、{7}と{5, 1}に分割される。
（7）{5, 1}が、{5}と{1}に分割される。
（8）{5}と{1}が、{1, 5}に結合される。
（9）{7}と{1, 5}が、{1, 5, 7}に結合される。
（10）{2, 3, 8}と{1, 5, 6}が、{1, 2, 3, 5, 7, 8}に結合される（ソート完了）。
☆ ☆ ☆
今回は、「マージソート」というアルゴリズムを取り上げました。
この連載は、今回で最終回です。これまで記事をお読みいただいた読者の皆様に、この場をお借りして厚く御礼申し上げます。
それでは、またどこかでお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
「リスト」というデータ構造｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
クイックソートのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (2) 二分探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
