このページでは、ソートアルゴリズムの１つである「挿入ソート」について解説し、続いてC言語での「挿入ソート」の実装プログラム例を紹介していきます。
また、この「挿入ソート」を「再帰呼び出し」で実現する考え方について解説し、そのプログラム例の紹介も行います。
「挿入ソート」だけでなく、アルゴリズムを「再帰呼び出し」で実現する考え方についても学んでいただけると思います！
ソートがどのようなものであるかは下記ページの冒頭で解説していますので、まずソートについて知りたい方は先にこちらを読んでみてください。
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
Contents
挿入ソートとは
挿入ソートとは前述の通り、ソートアルゴリズムの１つです。
挿入ソートの特徴
挿入ソートには下記のような特徴があります。
- アルゴリズムが簡単！
- 使用メモリが少ない（配列一つ分でソートできる）
- 処理速度が遅い
選択ソート同様に、アルゴリズムが簡単で直感的にも理解しやすいので、ソートアルゴリズムを最初に学ぶには最適なアルゴリズムです。
スポンサーリンク
挿入ソートの考え方
挿入ソートは、その名の通り「データの挿入」を繰り返すことでソートを行うアルゴリズムです。
挿入ソートでは、まずデータ全体を「ソート済みの集合」と「未ソートの集合」の２つに分割して考えます。
そして「未ソートの集合」のデータを１つ選択し、そのデータを「ソート済みの集合」に挿入します。
で、この時の挿入では、挿入によってソート済みの状態が崩れないように挿入するのがポイントです。
このように挿入することで「ソート済みの集合」のデータ数が１つ増え、「未ソートの集合」のデータ数が１つ減ることになります。
つまり、このような挿入を繰り返すことで、どんどんデータが「ソート済みの集合」に移動し、最終的にはデータ全体が「ソート済みの集合」となります。
「ソート済みの集合」にデータが全て移動したら全体のソートが完了したことになります。
これが挿入ソートの考え方です。
要は、”まだソートしていないデータ” を “ソート済みのデータの中の適切な位置に挿入する” ことでソートを行うアルゴリズムになります。
文章で表せば、挿入ソートは与えられたデータの集合に対し、下記の考え方でソートを行うアルゴリズムでになります。
- データ全体を「ソート済みの集合」と「未ソートの集合」に分割する
- 「未ソートの集合」からデータを１つ選択する
- 選択したデータを「ソート済みの集合」に挿入する
- この時、ソート済みの状態を崩さないように挿入する
- これにより「ソート済みの集合」にデータが増える
- さらに「未ソートの集合」のデータが減る
- 3. により全データが「ソート済みの集合」となったら終了、なっていない場合は 2. に戻る
挿入ソートの流れ
続いて、下の図のようなデータの集合を挿入ソートでソートしていく処理の流れを解説していきたいと思います。
ソートは「昇順」に行うものとして解説していきます。降順にソートしたい場合は、大小関係を逆に読み取りながら解説を読んでいただければ良いと思います。
データ全体を「ソート済みの集合」と「未ソートの集合」に分割する
まずは、データ全体を「ソート済みの集合」と「未ソートの集合」の２つに分割します。
このページでは、この集合の分割は下記のように行うものとして説明していきたいと思います。
- ソート済みの集合：データ全体の先頭のデータのみ
- 未ソートの集合：残りのデータ
具体的には下の図のように２つの集合に分割されることになります。
「ソート済みの集合」にはデータが１つしか存在していないので、”既にソートされている” と考えることができます。
今回は、データ全体の分割で「ソート済みの集合」のデータ数を “１つのみ” にしていますが、データの並びによっては「ソート済みの集合」に “複数のデータ” が存在するように分割するようなことも可能です。
例えばデータ全体が下の図のような並びであれば、既に前方の４つのデータは昇順にソートされています。
ですので、最初に「ソート済みの集合」に４つのデータが存在するように考えて挿入ソートを行うようなことも可能です。最初に「ソート済みの集合」が多い方が効率が良いです。
ただし、どのデータまでがソート済みであるかを調べる必要があり、プログラミングが（若干ですが）複雑になってしまいます。
今回はできるだけ簡単に分かりやすく解説＆プログラミングしたいので、「ソート済みの集合」は “データ全体の先頭のデータのみ” の状態からソートを行う方針で解説させていただきます。
スポンサーリンク
１回目のソート
では、現状の「ソート済みの集合」と「未ソートの集合」に対し、挿入ソートを行っていきます。
「未ソートの集合」からデータを１つ選択する
まずは「未ソートの集合」からデータを１つ選択します。
「未ソートの集合」のデータであれば、どのデータを選んだとしても最終的にソートを行うことができます。
このページでは、このデータとして「未ソートの集合」の “先頭” のデータを選択するようにしたいと思います。ですので、今回は 1 のデータが選択されることになります。
これは、考え方が簡単であることと、おそらくこの選択方法が一番効率が良いからです。具体的に言うと、実際にデータを「ソート済みの集合」に挿入する時の効率が良いです。
選択したデータを「ソート済みの集合」に挿入する
続いて、先程選択したデータをソート済みの集合に挿入していきます。
この挿入時におけるポイントは、”ソート済みの状態を崩さないように” 挿入することです。
要は、挿入後もソートされている状態になるようにデータを挿入します。
これを行うためには、まずは「ソート済みの集合」のどの位置にデータを挿入するかを決める必要があります。具体的には、選択したデータと各データの大小関係を比較しながら、どこに挿入するかを決定します。
今回は「ソート済みの集合」が１つで、そのデータが 4、さらに選択したデータが 1 なので、4 の前に 1 を挿入します（昇順ソートなので）。
データが挿入されたことにより「ソート済みの集合」のデータが１つ増えたことになります。もちろん、ソート済みの状態を崩さないようにデータの挿入を行ったので「ソート済みの集合」のデータはソートされた状態になっています。
また、データが１つ「ソート済みの集合」に移動したので、「未ソートの集合」からはデータが１つ減ったことになります。
次は、この新たな「ソート済みの集合」と「未ソートの集合」に対して再度ソートを行います。
２回目のソート
続いて、１回目のソート後の「ソート済みの集合」と「未ソートの集合」に対し、再度挿入ソートを行っていきます。
「未ソートの集合」からデータを１つ選択する
前述の通り、このデータの選択では「未ソートの集合」の “先頭” のデータを選択します。
ですので、今回はデータ 3 を選択します。
選択したデータを「ソート済みの集合」に挿入する
まずは「ソート済みの集合」のどの位置に選択したデータを挿入するかを決めます。
今回は選択したデータが 3 なので、昇順にソートするのであれば、データ 1 とデータ 4 の間が挿入すべきデータの位置となります。
なので、データ 3 をデータ 1 とデータ 4 の間に挿入します。
これにより、「ソート済みの集合」のデータがまた１つ増え「未ソートの集合」のデータがまた１つ減ることになります。
次は、この新たな「ソート済みの集合」と「未ソートの集合」に対して再度ソートを行います。
３回目以降のソート
で、３回目以降も同様の方法でソートを行っていきます。ソートを行うたびに「ソート済みの集合」が増え、「未ソートの集合」が減ることになります。
最終的にはデータの全てが「ソート済みの集合」に存在することになります。こうなると、データ全てをソートし終わったことになるので、その時点でソートは完了です。
スポンサーリンク
挿入ソートのプログラム
次に、挿入ソートのプログラムのソースコードの紹介と、その解説をしていきたいと思います。
ソースコード
挿入ソートを行うプログラムのソースコード例は下記になります。
#include <stdio.h>
/* データの数 */
#define NUM 10
void insertionSort(int a[], int num) {
int select; /* 選択したデータの位置 */
int insert; /* データを挿入する位置 */
int data; /* 挿入するデータ */
int sorted; /* ソート済みの集合のデータ数 */
int i;
/* 初期段階でのソート済みの集合の数は１つ */
sorted = 1;
/* 全データがソート済みの集合に移動するまでソートを繰り返す */
while (sorted < num) {
/* 未ソートの集合のデータを１つ選択 */
select = sorted; /* 未ソートの集合の先頭 */
data = a[select];
/* ソート済み集合の中から選択したデータを挿入する位置を決定 */
for (i = 0; i < sorted; i++) {
if (a[i] > data) {
/* 昇順に並べるので、dataより大きいデータの手前に挿入 */
break;
}
}
/* 挿入する位置を記憶 */
insert = i;
/* 挿入する位置から選択した要素の１つ前までの要素を全て１つ後ろにずらす */
for (i = select - 1; i >= insert; i--) {
a[i + 1] = a[i];
}
/* 挿入する位置にデータを格納 */
a[insert] = data;
/* ソート済みの集合にデータが挿入されたのでsortedを+1 */
sorted++;
}
}
/* 配列を初期化する関数 */
void initArray(int a[]) {
a[0] = 5;
a[1] = 0;
a[2] = 9;
a[3] = 7;
a[4] = 1;
a[5] = 6;
a[6] = 3;
a[7] = 8;
a[8] = 4;
a[9] = 2;
}
/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
int i;
for (i = 0; i < num; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
int main(void) {
int array[NUM];
/* 配列を初期化 */
initArray(array);
/* ソート前の配列の表示 */
printArray(array, NUM);
/* 選択ソート */
insertionSort(array, NUM);
/* ソート後の配列の表示 */
printArray(array, NUM);
return 0;
}ソースコードの解説
では、ソースコードの解説を行っていきたいと思います。挿入ソート自体が割と簡単なアルゴリズムなので、説明不要な方はこの節はスキップしていただいて問題ないと思います！
insertionSort 関数
ここまで解説してきた「挿入ソート」は insertionSort 関数で行っています。
insertionSort 関数の引数 a はソートしたいデータが格納された配列で、引数 num はそのデータの個数になります。
データ全体を「ソート済みの集合」と「未ソートの集合」に分割する
データ全体を２つの集合に分割にする処理は下記で行っています。あまり、集合を分割しているような処理には見えないかもしれませんが…。
sorted = 1;sorted は「ソート済みの集合」のデータ数を管理するための変数です。したがって、データ全体 a を下記の２つの集合として考えることができます。
- ソート済みの集合：
a[0]からa[sorted - 1] - 未ソートの集合：
a[sorted]からa[num - 1]
初期段階では「ソート済みの集合」は “データ全体の先頭のみ” なので、上記で sorted に 1 を格納しています。なので、a[0]と a[1] 〜 a[num - 1] の２つの集合に分割していることになります。
ソートの繰り返し
また、挿入によるソートは下記の while ループの中で実行しています。全データが「ソート済みの集合」に移動するまで繰り返すため while の継続条件は sorted < num としています。
while (sorted < num) {
/* 略 */
}「未ソートの集合」からデータを１つ選択する
下記では「未ソートの集合」の中からデータを選択する処理を行っています。
sorted が「ソート済みの集合」のデータ数を表すため、a[0] 〜 a[sorted - 1] までは「ソート済みの集合」のデータであると言えます。なので、「未ソートの集合」の先頭の位置は sorted になります。
select = sorted; /* 未ソートの集合の先頭 */
data = a[select];選択したデータを「ソート済みの集合」に挿入する
さらに、下記では、選択したデータを「ソート済みの集合」のどの位置に挿入するかを決めています。
for (i = 0; i < sorted; i++) {
if (a[i] > data) {
/* 昇順に並べるので、dataより大きいデータの手前に挿入 */
break;
}
}
/* 挿入する位置を記憶 */
insert = i;今回は昇順にソートを行うため、「ソート済みの集合の先頭」、つまり配列の先頭から “選択したデータよりも大きい” 値を見つけたら、その位置にデータを挿入するようにしています。
実際にデータの挿入を行っているのは下記部分になります。
for (i = select - 1; i >= insert; i--) {
a[i + 1] = a[i];
}
/* 挿入する位置にデータを格納 */
a[insert] = data;要は、まず “挿入位置” から “選択したデータがあった位置の１つ手前” までのデータを１つずつ後ろにずらし、
続いて “挿入位置” にデータを格納することでデータの挿入を実現しています。
このデータの挿入は、例えば下の図のように、”選択したデータ” から “挿入位置” までの各データを、前後のデータと交換するような処理でも実現することができます。
結構他のサイトさんだとこの方法で解説されているところも多かったので、補足として解説しておきました。やり方は違いますが、目的はどちらも「挿入すべき位置にデータを挿入すること」で一緒です。
「ソート済みの集合」のデータ数をインクリメント
データの挿入を行うと、「ソート済みの集合」のデータ数が１増えるので、データの挿入後は sorted の値を +1 しています。
スポンサーリンク
再帰呼び出しを用いた「挿入ソート」
続いては再帰呼び出しを用いて「挿入ソート」を実現する考え方について解説していきます。
再帰呼び出しを用いた挿入ソート関数の作り方
例として、下の図のようなデータの集合を用いて解説していきたいと思います。
もし、このデータの集合の “最後尾のデータ以外” が “何らかの方法” でソートされたとしましょう。
この場合、「未ソートの集合」のデータは最後尾のデータ１つのみと考えることができます。
ですので、「未ソートの集合」のデータを１回「ソート済みの集合」に挿入してやれば、データ全体がソート完了したことになりますね！（もちろんソート済みの状態を崩さないように挿入する必要があります）
つまり、挿入ソートは下記のように考えることができます。
- “最後尾のデータ以外” をソートする
- 最後尾のデータを「ソート済みの集合」に挿入する
挿入ソートのプログラムでは、insertionSort 関数の while ループで「データの挿入」つまり、上記の後者の処理を “繰り返す” ことでソートを行いました。
逆に考えると、後者の処理は、挿入ソートのプログラムで紹介した insertionSort 関数の while ループの内側の処理を一回実行することで実現できますね！
では「”最後尾のデータ以外” をソートする」はどのように実現すれば良いでしょうか？
これも挿入ソートで行えば良いです！
つまり、挿入ソートの中で “最後尾のデータ以外” をソートするために挿入ソートを実行します。つまり挿入ソートの再帰呼び出しです。
この考えに基づくと、挿入ソートは下記のように考えることができます。
- “最後尾のデータ以外” を “挿入ソート” でソートする
- 最後尾のデータを「ソート済みの集合」に挿入する
そして、この考えに基づいた挿入ソートを行う関数 insertionSort 関数は次のようになります。
void insertionSort(int a[], int num) {
int select; /* 選択したデータの位置 */
int insert; /* データを挿入する位置 */
int data; /* 挿入するデータ */
int sorted; /* ソート済みの集合のデータ数 */
int i;
if (num <= 1) {
/* データ数1以下の場合はすでにソート済み */
return;
}
/* 挿入ソートでnum-1個のデータをソートする */
insertionSort(a, num - 1);
/* 上記のソートによりnum-1個はソート済み */
sorted = num - 1;
/* 未ソートの集合のデータを１つ選択 */
select = sorted; /* 未ソートの集合の先頭 */
data = a[select];
/* ソート済み集合の中から選択したデータを挿入する位置を決定 */
for (i = 0; i < sorted; i++) {
if (a[i] > data) {
/* 昇順に並べるので、dataより大きいデータの手前に挿入 */
break;
}
}
/* 挿入する位置を記憶 */
insert = i;
/* 挿入する位置から選択した要素の１つ前までの要素を全て１つ後ろにずらす */
for (i = select - 1; i >= insert; i--) {
a[i + 1] = a[i];
}
/* 挿入する位置にデータを格納 */
a[insert] = data;
}「”最後尾のデータ以外” を “挿入ソート” でソートする」を行っているのは insertionSort 関数の下記部分になります。
if (num <= 1) {
/* データ数1以下の場合はすでにソート済み */
return;
}
/* 挿入ソートでnum-1個のデータをソートする */
insertionSort(a, num - 1);データ数 num が 1 の場合は、すでにソート済みであると考えることができるので、その場合はソートが完了したとして即座に関数を終了するようにしています。
また、「最後尾のデータを「ソート済みの集合」に挿入する」を行っているのは insertionSort 関数の下記部分になります。
/* 上記のソートによりnum-1個はソート済み */
sorted = num - 1;
/* 未ソートの集合のデータを１つ選択 */
select = sorted; /* 未ソートの集合の先頭 */
data = a[select];
/* ソート済み集合の中から選択したデータを挿入する位置を決定 */
for (i = 0; i < sorted; i++) {
if (a[i] > data) {
/* 昇順に並べるので、dataより大きいデータの手前に挿入 */
break;
}
}
/* 挿入する位置を記憶 */
insert = i;
/* 挿入する位置から選択した要素の１つ前までの要素を全て１つ後ろにずらす */
for (i = select - 1; i >= insert; i--) {
a[i + 1] = a[i];
}
/* 挿入する位置にデータを格納 */
a[insert] = data;上記では、挿入ソートのプログラムで紹介した insertionSort 関数の while ループの内側の処理を一回実行しているだけです。ですので、何やってるか分からない場合は挿入ソートのプログラムの解説を読んでみてください。
挿入ソートでの再帰呼び出しの動作
ポイントは、再帰呼び出し時のソート範囲を “最後尾のデータ以外” とすることで、ソート範囲を１段階狭めているところです。
挿入ソートの中で挿入ソートを再帰呼び出しするようにすることで、挿入ソートを実行すると、その中でどんどん挿入ソートが実行されていくことになります。
で、この再帰呼び出しの際に１段階ずつソートする範囲が狭められていくので、いずれはデータ数が１つのみになります（これは元々のデータ全体の先頭のデータになります）。
ソートする範囲のデータ数が１つになったということは、その範囲のデータはすでにソート済みの状態であると言えるので、これ以降は挿入ソートを再帰呼び出しする必要はありません。
なので、データ数が１つの場合の挿入ソートは即座に終了させるようにしています。
再帰呼び出しせずに挿入ソートが終了するので、ここからは再帰呼び出しの折り返しが始まります。
ここで下記の挿入ソートの考え方を思い出しましょう！
- “最後尾のデータ以外” をソートする
- 最後尾のデータを「ソート済みの集合」に挿入する
つまり、ソート範囲のデータ数が１つのソートが完了しているので、ソート範囲のデータ数が２つのソートでは後者の「データの挿入」を１回行えばソートが完了します。
さらに、ソート範囲のデータ数が２つのソートが完了すれば、ソート範囲のデータ数が３つのソートでも「データの挿入」を１回行えばソートが完了します。
以降も同様ですね！ソート範囲のデータ数が N - 1 のソートが完了すれば、ソート範囲のデータ数が N のソートでは「データの挿入」を１回行えばソートが完了します。
このように、どんどん再帰呼び出しがリターンし、いずれは最初の挿入ソートの処理に戻ります。で、この時には “最後尾のデータ以外” がソートされた状態になりますので、あとは最後尾のデータを挿入してやれば、データ全体がソートされたことになります。
スポンサーリンク
ソートを再帰呼び出しで実現する方法
要は、ソートを再帰呼び出しで実現するためには、下記のような考え方で関数を作成すれば良いです。
- データの範囲を１段階狭めて “再帰呼び出し” でソートを行う
- ソート済みになったら再帰呼び出ししない（この場合はデータ数が
1になったら） - ソートを１段階だけ進める
つまり、まずは「後１段階だけソートを行えばデータ全体がソートされる」という状態をイメージし、
その状況でソートを行うために必要な処理を記述します。この処理が 3. になります。
/* 上記のソートによりnum-1個はソート済み */
sorted = num - 1;
/* 未ソートの集合のデータを１つ選択 */
select = sorted; /* 未ソートの集合の先頭 */
data = a[select];
/* ソート済み集合の中から選択したデータを挿入する位置を決定 */
for (i = 0; i < sorted; i++) {
if (a[i] > data) {
/* 昇順に並べるので、dataより大きいデータの手前に挿入 */
break;
}
}
/* 挿入する位置を記憶 */
insert = i;
/* 挿入する位置から選択した要素の１つ前までの要素を全て１つ後ろにずらす */
for (i = select - 1; i >= insert; i--) {
a[i + 1] = a[i];
}
/* 挿入する位置にデータを格納 */
a[insert] = data;さらに、「後１段階だけソートを行えばデータ全体がソートされる」という状態になるまで再帰呼び出しでソートを行うようにします。この処理が 1. になります。
/* 挿入ソートでnum-1個のデータをソートする */
insertionSort(a, num - 1);で、再帰呼び出しを単に行うと永遠に再帰呼び出しが実行されることになってしまうため、ソートが完了していることが自明な場合は再帰呼び出しを行わないようにします。
データ数が 1 の場合はソートが完了していることが自明なので、データ数が 1 になったら再帰呼び出しをしないようにします。この処理が 2. になります。
if (num <= 1) {
/* データ数1以下の場合はすでにソート済み */
return;
}再帰呼び出しでソートを行う場合は、上記のように考えて関数を作成すれば大体上手くいくと思います。
実質的に実装方法を考える必要があるのは 3. だけですので、「データ全体のソート」ではなく「１段階だけのソート」の実装方法だけを考慮すれば良いことになり、かなり簡単にソート関数を作成できます！
また、説明は省略しますが、逆の視点で考えて下記の方法で再帰呼び出しによるソートを行うことできます。
- ソートを１段階だけ進める
- データの範囲を１段階狭めて “再帰呼び出し” でソートを行う
- ソート済みになったら再帰呼び出ししない（この場合はデータ数が
1になったら）
この場合は、ソートを１段階進めてから残りのソートを再帰呼び出しで実行します。
まとめ
このページでは挿入ソートについて解説しました。
挿入ソートは下記の考え方でデータを並べ替えるソート方法になります。
- データ全体を「ソート済みの集合」と「未ソートの集合」に分割する
- 「未ソートの集合」からデータを１つ選択する
- 選択したデータを「ソート済みの集合」に挿入する
- この時、ソート済みの状態を崩さないように挿入する
- これにより「ソート済みの集合」にデータが増える
- さらに「未ソートの集合」のデータが減る
- 3. により全データが「ソート済みの集合」となったら終了、なっていない場合は 2. に戻る
要は「未ソートの集合のデータ」を「ソート済みの集合」の適切な位置に挿入していくことでソートを行うアルゴリズムになります。
割と単純なアルゴリズムということもありましたので、今回はソートを再帰呼び出しで実現する時の考え方についても一緒に解説しています。
この考え方で他のソートも再帰呼び出しで実現できると思いますので（無理なものもあるかも）、再帰呼び出しでのソート実現時に参考にしていただければと思います！
本サイトでは、挿入ソート以外にも下記のソートについても解説しています。
- クイックソート
- マージソート
- 選択ソート
下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
