はじめに
本講義は「C言語の文法は理解したけど、目的のプログラムを作るための方法（アルゴリズム）がわからない！」といった方が対象です。
このためC言語を用いて、基本的なアルゴリズムについて理解することを目標としています。
C言語が分からない、プログラミングそのものが初心者だという方は、「爆速C言語入門」で学習してからこの記事を見ることをおすすめします！
今回は、前回紹介しきれなかった代表的なソートアルゴリズムを2つ紹介します。
実行について
以降ではソートアルゴリズムを説明する際に、各ソートアルゴリズムを関数として作成したものを載せています。
ここでは、以降で説明する各ソート関数を実行する例として「main関数」を載せておきます。
#include <stdio.h>
#include <stdlib.h>
//ソートアルゴリズム(2)
//プロトタイプ宣言
void vdPrintData(int, int[]);
//以下,利用するアルゴリズムのコメントアウトをそれぞれ2つ消す
//void vdQuickSort(int, int[]); //クイックソート
//void vdRecursiveQS(int, int, int[]); //クイックソート(再帰部分)
//void vdMargeSort(int, int[]); //マージソート
//void vdRecursiveMS(int, int, 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); //初期状態の表示
//ソートを行う
//以下,利用するアルゴリズムのコメントアウトを消す
//vdQuickSort(iDataNum, aiData); //クイックソート
//vdMargeSort(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");
}
クイックソート
クイックソートは「ソート対象のデータ列の細分化を繰り返すことでソートするアルゴリズム」です。
オーダーはO(N^x)の壁を破り、平均でO(NlogN)なので、データ数Nが大きくなるほど優位性が高くなります。
高速に動作することを目指したアルゴリズムであるため、この名前になっています。 一般的には再帰関数が用いられます。
クイックソートは次の手順でソートします。
- データ列が整列されていれば再帰を終了する
- 基準値を決める
- 基準値より小さい値と大きい値にデータ列を分割する（配列の左右に固める）
- 3により得られたデータ列それぞれに1-4を再帰的に行う
次の図では、実際にソートされていく様子を示します。
クイックソートをC言語で実装すると次のようになります。
//クイックソート(実行)
void vdQuickSort(int iNum, int aiData[]) {
//配列の全要素に対して再帰的にクイックソートを実行
vdRecursiveQS(0, iNum - 1, aiData);
}
//クイックソート(再帰部分)
void vdRecursiveQS(int iTop, int iBottom, int aiData[]) {
int iTempLeft = iTop; //探索用の添え字(左側)
int iTempRight = iBottom; //探索用の添え字(右側)
int iPivot; //基準値
int iSwap; //交換用,一時的に値を記憶する
//終了条件:データ列が整列されている場合
//=配列の先頭と終端が一致,もしくは逆転している場合
if (iTop >= iBottom) {
return;
}
//基準値を決める
iPivot = aiData[(iTop + iBottom) / 2];
//基準値より小さい値と大きい値にデータ列を分割する
//添え字の順序が逆転するまでループ処理
while (1) {
//移動の必要なデータを探索
for (; aiData[iTempLeft] < iPivot; iTempLeft++); //基準より大きい値を探索
for (; aiData[iTempRight] > iPivot; iTempRight--); //基準より小さい値を探索
//添え字の順序が逆転
if (iTempLeft >= iTempRight) {
break;
}
//データを移動(入替)
iSwap = aiData[iTempLeft];
aiData[iTempLeft] = aiData[iTempRight];
aiData[iTempRight] = iSwap;
iTempLeft++;
iTempRight--;
}
//分割したデータを再帰的に処理
vdRecursiveQS(iTop, iTempLeft - 1, aiData);
vdRecursiveQS(iTempRight + 1, iBottom, aiData);
}
マージソート
マージソートは「整列した複数のデータ列を統合（マージ）する際、それぞれの先頭のうち最も小さいものから順に並べると整列するという分割統治法の考え方を用いてソートするアルゴリズム」です。
それぞれを統合（マージ）する作業は並列化することが可能です。
最悪計算量はO(NlogN)でクイックソートよりも高速ですが、ランダムデータに対するソートではクイックソートの方が高速です。
マージソートは次の手順でソートします。
- データ列の要素数が1の場合終了
- データ列を2分割する
- 分割した2つの配列を先頭から順にマージして1つの配列にする
次の図では、実際にソートされていく様子を示します。
マージソートをC言語で実装すると次のようになります。
void vdMargeSort(int iNum, int aiData[]) {
//計算領域を確保
int* aiCalc = (int*)malloc(sizeof(int) * iNum);
//計算領域を確保できなかった場合
if (aiCalc == NULL) {
return;
}
//配列の全要素に対して再帰的にマージソートを実行
vdRecursiveMS(0, iNum - 1, aiData, aiCalc);
//計算領域を解放
free(aiCalc);
}
void vdRecursiveMS(int iTop, int iBottom, int aiData[], int aiCalc[]) {
int iMid; //中間点
int iTempLeft; //左側配列の先頭要素の添え字
int iTempRight; //右側配列の先頭要素の添え字
int iTempCalc = 0; //計算用配列の添え字
int iTempCnt; //配列更新用の添え字
//配列の要素数が1つ以下の場合は配列を変更しない
if (iTop >= iBottom) {
return;
}
//配列の要素数が2つ以上の場合,配列を分割
iMid = (iBottom + iTop) / 2;
vdRecursiveMS(iTop, iMid, aiData, aiCalc);
vdRecursiveMS(iMid + 1, iBottom, aiData, aiCalc);
//ソート済みの2配列から計算領域に取り出す
iTempLeft = iTop;
iTempRight = iMid + 1;
//左右の配列のどちらかが取り出し終えるまで
while (iTempLeft <= iMid && iTempRight <= iBottom) {
//左右の先頭の値を比較,小さい方を格納データとして取り出し
if (aiData[iTempLeft] < aiData[iTempRight]) {
aiCalc[iTempCalc++] = aiData[iTempLeft++];
}
else {
aiCalc[iTempCalc++] = aiData[iTempRight++];
}
}
//取り出し終えていない配列をすべて格納
if (iTempLeft > iMid) {
while (iTempRight <= iBottom) {
aiCalc[iTempCalc++] = aiData[iTempRight++];
}
}
else {
while (iTempLeft <= iMid) {
aiCalc[iTempCalc++] = aiData[iTempLeft++];
}
}
//計算領域に格納したデータで配列を更新
for (iTempCnt = 0; iTempCnt < iTempCalc; iTempCnt++) {
aiData[iTop + iTempCnt] = aiCalc[iTempCnt];
}
}
おすすめの参考書
学生時代に読み易かったものを挙げておきます。
 | 新品価格 |
 | 新品価格 |
最後に
今回紹介したクイックソートが一番実用されているように感じます。
ソートアルゴリズムについては、他にもたくさんありますが、2つの記事で必要な範囲は網羅しているかなという印象です。
コメント