はじめに
本講義は「C言語の文法は理解したけど、目的のプログラムを作るための方法（アルゴリズム）がわからない！」といった方が対象です。
このためC言語を用いて、基本的なアルゴリズムについて理解することを目標としています。
C言語が分からない、プログラミングそのものが初心者だという方は、「爆速C言語入門」で学習してからこの記事を見ることをおすすめします！
今回はソートについて基本と簡単なソートアルゴリズムについて解説します。
ソートとは？
ソートとはデータに対してある基準に基づいて並び替えを行うことです。
例えば次のような基準に基づいて並び替えを行います。
- 数値の小さい順（昇順）
- 数値の大きい順（降順）
- アルファベット順
- 日付順
これらの基準に基づいてソートする方法のことをソートアルゴリズムといい、様々なものが提唱されています。
本講義では代表的なソートアルゴリズムのうち、考え方の容易な次の3つのソートアルゴリズムについて説明します。
- バブルソート
- 選択ソート
- 挿入ソート
実行について
以降ではソートアルゴリズムを説明する際に、各ソートアルゴリズムを関数として作成したものを載せています。
ここでは、以降で説明する各ソート関数を実行する例として「main関数」を載せておきます。
#include <stdio.h>
//ソートアルゴリズム(1)
//プロトタイプ宣言
void vdPrintData(int, int[]);
//以下,利用するアルゴリズムのコメントアウトを消す
//void vdBubbleSort(int, int[]); //バブルソート
//void vdBubbleSortEx(int, int[]); //バブルソート改善版
//void vdSelectionSort(int, int[]); //選択ソート
//void vdInsertionSort(int, int[]); //挿入ソート
//main関数
int main() {
//ソート対象のデータ
int aiData[] = { 6,9,4,2,8,7,1,0,5,3 }; //ソート対象の配列
int iDataNum = sizeof(aiData) / sizeof(int); //配列の要素数
vdPrintData(iDataNum, aiData); //初期状態の表示
//ソートを行う
//以下,利用するアルゴリズムのコメントアウトを消す
//vdBubbleSort(iDataNum, aiData); //バブルソート
//vdBubbleSortEx(iDataNum, aiData); //バブルソート改善版
//vdSelectionSort(iDataNum, aiData); //選択ソート
//vdInsertionSort(iDataNum, aiData); //挿入ソート
vdPrintData(iDataNum, aiData); //ソート結果の表示
return 0;
}
//配列を表示
void vdPrintData(int iNum, int aiData[]){
int iCntData; //要素の添え字
//配列の全要素を先頭から順に出力
for(iCntData = 0; iCntData < iNum; iCntData++){
printf("%d ", aiData[iCntData]);
}
//改行出力
printf("\n");
}
//以下,各ソートアルゴリズムをコピペする
バブルソート
バブルソートは「隣り合う2つのデータを比較して入れ替えるという操作を繰り返すことでソートするアルゴリズム」で、アルゴリズムが単純で容易に実装できることが特徴です。
並び替えの過程が気泡（バブル）が水の中から水面に浮かび上がってくる様子に似ているためこの名前が付けられました。
バブルソートでは次の手順でソートを行います。（要素はN個とする）
- 「1番目の要素」と「2番目の要素」を比較して、「1番目の要素」の方が大きければ交換する
- 「2番目の要素」と「3番目の要素」を比較して、「2番目の要素」の方が大きければ交換する
- 同様の処理を「N-1番目」と「N番目」の比較を行うまで順に繰り返す（「N-1回」繰り返すこととなる）
- 結果として「N番目の要素」は「N個の要素」の中で最も大きいため「ソート済」とする
- 「ソート済」でない残りの要素について（１）から順に繰り返し、「N-1個の要素」が「ソート済」になればソート終了
次の図では、実際にソートされていく様子を示します。
バブルソートをC言語で実装すると次のようになります。
//バブルソート
void vdBubbleSort(int iNum, int aiData[]){
int iSortedCnt; //ソートされた要素数
int iUnSortedCnt; //ソートされていない要素の添え字
int iSwap; //交換用,一時的に値を記憶する
//決定する要素数分ループ処理
//配列の右から順に要素数-1個決定すればよい
for(iSortedCnt = 0; iSortedCnt < iNum - 1; iSortedCnt++){
//決定していない要素を順番に比較
//左の要素を起点とするため,決定していない要素数-1回で良い
for(iUnSortedCnt = 0; iUnSortedCnt < iNum - iSortedCnt - 1; iUnSortedCnt++){
//左の要素が右の要素より大きい場合
if(aiData[iUnSortedCnt] > aiData[iUnSortedCnt + 1]){
//左の要素と右の要素を入れ替える
iSwap = aiData[iUnSortedCnt];
aiData[iUnSortedCnt] = aiData[iUnSortedCnt + 1];
aiData[iUnSortedCnt + 1] = iSwap;
}
}
}
}
バブルソートの改善
バブルソートでは、右側から1つずつ順番に決定していました。
しかし、実際には1周した時に「最後に交換した位置より後ろの要素」は「ソート済」です。これを踏まえてアルゴリズムを考えると次のようになります。
改善版のバブルソートでは次の手順でソートを行います。（要素はN個とする）
- 「1番目の要素」と「2番目の要素」を比較して、「1番目の要素」の方が大きければ交換する
- 「2番目の要素」と「3番目の要素」を比較して、「2番目の要素」の方が大きければ交換する
- 同様の処理を「N-1番目」と「N番目」の比較を行うまで順に繰り返す（「N-1回」繰り返すこととなる）
- 最後に交換した位置より後ろの要素を「ソート済」とする
- 「ソート済」でない残りの要素について（１）から順に繰り返し、「N-1個の要素」が「ソート済」になればソート終了
改善版のバブルソートをC言語で実装すると次のようになります。
//バブルソート(改善版)
void vdBubbleSortEx(int iNum, int aiData[]){
int iSortedCnt; //ソートされた要素数
int iUnSortedCnt; //ソートされていない要素の添え字
int iSwap; //交換用,一時的に値を記憶する
int iSwapPos; //最後に入れ替えた位置を記憶する
int iUnSortedMax; //ソートされていない要素の最大値
//最後に入れ替えた位置を末尾で初期化
//末尾より後ろは見る必要がない（整列していることにする）
iSwapPos = iNum - 1;
//決定する要素数分ループ処理
//配列の右から順に要素数-1個決定する
for(iSortedCnt = 0; iSortedCnt < iNum - 1; iSortedCnt++){
//決定していない要素の最大値を計算
//入れ替えた位置を初期化
iUnSortedMax = iSwapPos;
iSwapPos = 0;
//決定していない要素を順番に比較
for(iUnSortedCnt = 0; iUnSortedCnt < iUnSortedMax; iUnSortedCnt++){
//左の要素が右の要素より大きい場合
if(aiData[iUnSortedCnt] > aiData[iUnSortedCnt + 1]){
//左の要素と右の要素を入れ替える
iSwap = aiData[iUnSortedCnt];
aiData[iUnSortedCnt] = aiData[iUnSortedCnt + 1];
aiData[iUnSortedCnt + 1] = iSwap;
//入れ替えた位置を記憶
iSwapPos = iUnSortedCnt;
}
}
}
}
選択ソート
選択ソートは「全ての範囲から最小値を選んで先頭に置く。残りの範囲から最小値を選んで残りの範囲の先頭に置く。というのを繰り返してソートするアルゴリズム」です。
バブルソートと同様にアルゴリズムが単純で容易に実装できます。順番に小さな値を選んでいくことからこの名前が付けられています。
選択ソートでは次の手順でソートします。（要素はN個とする）
- 「N個の要素」の中で最も小さい数を選択し、「1番目の要素」と入れ替える。この時、「1番目の要素」は「ソート済」となる
- 「ソート済」の「1番目の要素」を除いた「N-1個の要素」の中で最も小さい数を選択し、「2番目の要素」と入れ替える。この時、「2番目の要素」は「ソート済」となる
- 同様に、「ソート済」の要素を除いた範囲で最も小さい数を選択し、範囲の最も左側と入れ替える手順を「N-1番目の要素」を入れ替えるまで繰り返す
次の図では、実際にソートされていく様子を示します。
選択ソートをC言語で実装すると次のようになります。
//選択ソート
void vdSelectionSort(int iNum, int aiData[]){
int iSortedRight; //ソートされた範囲の最右の要素の添え字
int iUnSortedCnt; //ソートされていない要素の添え字
int iSwap; //交換用,一時的に値を記憶する
int iMinCnt; //ソート対象範囲の最小値の添え字
int iMinNum; //ソート対象範囲の最小値
//決定する要素分ループ処理
//配列の左から順に要素数-1個決定すればよい
for(iSortedRight = 0; iSortedRight < iNum - 1; iSortedRight++){
//最小値を初期化
//決定した要素の右隣を暫定的に最小値とする
int iMinCnt = iSortedRight;
int iMinNum = aiData[iSortedRight];
//決定していない要素を順番に比較
//暫定的に最小値とした要素の右隣から最後の要素まで
for(iUnSortedCnt = iSortedRight + 1; iUnSortedCnt < iNum; iUnSortedCnt++){
//添え字位置の要素が最小値より小さい場合
if(aiData[iUnSortedCnt] < iMinNum){
//最小値を更新する
iMinCnt = iUnSortedCnt;
iMinNum = aiData[iUnSortedCnt];
}
}
//得られた最小値をソートされた範囲の右に置く
iSwap = aiData[iSortedRight];
aiData[iSortedRight] = aiData[iMinCnt];
aiData[iMinCnt] = iSwap;
//ソートされた範囲を1つ増やす(for文の最後の処理)
}
}
挿入ソート
挿入ソートは「整列済みのデータの中に、未整列のデータを1つ1つ適切な位置に挿入するソートアルゴリズム」です。
データを1つ1つ挿入するのでこの名前になっています。
挿入ソートでは次の手順でソートします。（要素はN個とする）
- 「1番目の要素」を「整列済データ」とし、残りの要素を「未整列データ」とする
- 「未整列データ」のうち「最左の要素」を「整列済データ」と比較し、適切な位置に挿入する
- 「整列済データ」が一つ増える
- 全てのデータが「整列済データ」になるまで繰り返す
次の図では、実際にソートされていく様子を示します。
選択ソートをC言語で実装すると次のようになります。
//挿入ソート
void vdInsertionSort(int iNum, int aiData[]){
int iSortedRight; //ソートされた範囲の最右の要素の添え字
int iInsertCnt; //挿入位置の添え字
int iSwap; //交換用,一時的に値を記憶する
//決定する要素分ループ処理
//最左の要素は最初からソートされていると考え,残りのN-1個を決定する
for(iSortedRight = 0; iSortedRight < iNum - 1; iSortedRight++){
//挿入位置を探索
//ソートされた範囲の右から順に探索
iInsertCnt = iSortedRight + 1;
//挿入する要素>左の要素になる位置を見つけたら終了
//挿入位置が0の場合先頭のため終了
while(aiData[iInsertCnt] < aiData[iInsertCnt - 1] && iInsertCnt > 0){
//挿入する要素<左の要素の場合,値を交換
iSwap = aiData[iInsertCnt];
aiData[iInsertCnt] = aiData[iInsertCnt - 1];
aiData[iInsertCnt - 1] = iSwap;
//挿入する要素の位置が一つ左にずれる
iInsertCnt--;
}
//ソートされた範囲を1つ増やす(for文の最後の処理)
}
}
おすすめの参考書
学生時代に読み易かったものを挙げておきます。
 | 新品価格 |
 | 新品価格 |
最後に
ソートアルゴリズムについては、自分で実装することはめったにないと思いますが、「知っていて使える」のと「知らないで使う」のでは大きな差があります。
というか、後者の場合は論理的に何故そのソートアルゴリズムなのかを説明できないため、成果物に対しての評価が下がります。
知識としてはしっかり理解しておきましょう。
コメント