1. ソートの概念と応用
ソートとは、一連のレコードを特定のキーに基づいて昇順または降順に並べ替える操作です。ソートアルゴリズムにはいくつかの重要な特性があります。
- 安定性：ソート前のシーケンスに同じキーを持つ複数のレコードが存在する場合、ソート後もこれらのレコードの相対的な順序が維持される場合、そのアルゴリズムは「安定」です。例えば、元のシーケンスで
r[i] == r[j]かつi < jである場合、ソート後もr[i]がr[j]の前に位置するなら、それは安定なソートです。 - 内部ソート：ソートに必要なすべてのデータ要素がメモリ内に収まるソート方法です。
- 外部ソート：データ要素が多すぎてメモリに一度に収まらないため、ソートプロセス中にデータを外部ストレージとやり取りする必要があるソート方法です。
ソートは日常生活で広く応用されています。価格の並べ替え、テストの点数のランキングなど、様々な場面で利用されます。
2. ソートアルゴリズムの実装
1. 挿入ソート
挿入ソートは、既にソートされた部分列に要素を一つずつ挿入していくことで、全体をソートするシンプルで直感的なアルゴリズムです。未ソートの要素を順に取り出し、既にソートされた部分列の適切な位置に挿入していくことで、最終的に完全にソートされた列を得ます。
1.1 直接挿入ソート
直接挿入ソートは、最も基本的な挿入ソートです。その考え方は、ソートされていないレコードを一つずつ、すでにソートされた列の適切な位置に挿入し、すべてのレコードが挿入されるまでこのプロセスを繰り返すことです。
これは、トランプを手札に並べるような操作に似ています。第 i 個の要素を挿入する際、array[0] から array[i-1] までの要素はすでにソートされています。この時、array[i] のキー値を array[i-1]、array[i-2] と順に比較し、挿入位置を見つけたら array[i] を挿入し、元の位置の要素を後ろにずらします。
直接挿入ソートの特性は以下の通りです。
- 要素の集合がよりソートされているほど、アルゴリズムの時間効率が高くなります。
- 時間計算量：O(N²)
- 空間計算量：O(1)。これは安定なソートアルゴリズムです。
- 安定性：安定
// 直接挿入ソートの実装
void insertionSort(int *data, int size) {
for (int i = 1; i < size; ++i) {
int currentValue = data[i];
int j = i - 1;
// ソート済み部分列の末尾から比較を開始し、適切な位置を見つける
while (j >= 0 && data[j] > currentValue) {
data[j + 1] = data[j]; // 要素を後ろにずらす
--j;
}
data[j + 1] = currentValue; // 要素を挿入
}
}
1.2 シェルソート
シェルソートは、直接挿入ソートを改良したもので、間隔（ギャップ）を導入することで効率を向上させます。まず、一定の間隔 gap を設定し、その間隔で離れた要素をグループ化して各グループ内でソートします。このプロセスを gap を徐々に小さくして繰り返し、最終的に gap が1になったときに、全体がソートされた状態になります。これは、gap が1でない段階では事前ソートを行い、最終的に高速な直接挿入ソートを実行するという考え方です。
シェルソートは、gap が1より大きい間は事前ソートを行い、配列をより「ソートに近づけ」ます。そして gap が1になった時点で、配列はほぼソート済みになっているため、直接挿入ソートが非常に高速になります。このように全体として最適化効果が得られます。一般的に、gap は gap = gap / 2 や gap = gap / 3 + 1 のように減少させ、最終的に gap = 1 になるまで続けます。
シェルソートの時間計算量は、gap の選び方によって複雑で、正確に計算するのが難しいですが、一般的には O(N1.3) 程度とされています。
// シェルソートの実装
void shellSort(int* arr, int len) {
int interval = len;
while (interval > 1) {
// ギャップを減少させる。ここでは gap/3 + 1 を使用
interval = interval / 3 + 1;
for (int i = 0; i <= len - interval; ++i) {
int endIdx = i;
int tempValue = arr[endIdx + interval];
// ギャップ分離れた要素間で挿入ソートを行う
while (endIdx >= 0) {
if (tempValue < arr[endIdx]) {
arr[endIdx + interval] = arr[endIdx];
endIdx -= interval;
} else {
break;
}
}
arr[endIdx + interval] = tempValue;
}
}
}
2. 選択ソート
選択ソートの基本的な考え方は、各ステップで未ソートのデータから最小（または最大）の要素を一つ選択し、それをシーケンスの先頭（または末尾）に配置していくことです。
2.1 直接選択ソート
直接選択ソートは、未ソートの部分列から最小（または最大）の要素を見つけ、それを部分列の先頭（または末尾）と交換します。このプロセスを、部分列のサイズが1になるまで繰り返します。
ここでは、同時に最小値と最大値を見つけて交換する最適化版を実装します。ただし、最大値が先頭にあり、最小値と交換した後、最大値の位置が変わってしまうという特殊ケースに注意が必要です。
// 要素を交換するヘルパー関数
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
// 最適化された直接選択ソート
void selectionSort(int* array, int length) {
int startIdx = 0;
int endIdx = length - 1;
while (startIdx < endIdx) {
int minIdx = startIdx;
int maxIdx = startIdx;
// 未ソート部分列から最小値と最大値のインデックスを見つける
for (int i = startIdx + 1; i <= endIdx; ++i) {
if (array[i] < array[minIdx]) {
minIdx = i;
}
if (array[i] > array[maxIdx]) {
maxIdx = i;
}
}
// 最小値を先頭に移動
swap(&array[startIdx], &array[minIdx]);
// 最大値が先頭にあった場合、minIdxがmaxIdxの位置を上書きしてしまう
// そのため、maxIdxの位置を修正する
if (startIdx == maxIdx) {
maxIdx = minIdx;
}
// 最大値を末尾に移動
swap(&array[endIdx], &array[maxIdx]);
++startIdx;
--endIdx;
}
}
2.2 ヒープソート
ヒープソートは、ヒープというデータ構造を利用したソートアルゴリズムで、選択ソートの一種です。ヒープを用いてデータを選択します。昇順でソートする場合、大頂ヒープを構築します。
ヒープソートは、ヒープの根（最大値）を最後の要素と交換し、ヒープサイズを一つ小さくして再度ヒープを調整するプロセスを繰り返します。これにより、最大値が徐々に末尾に移動していきます。
// ヒープを調整する関数（大頂ヒープ）
void heapify(int* heapArray, int size, int parentIdx) {
int largest = parentIdx;
int leftChild = 2 * parentIdx + 1;
int rightChild = 2 * parentIdx + 2;
if (leftChild < size && heapArray[leftChild] > heapArray[largest]) {
largest = leftChild;
}
if (rightChild < size && heapArray[rightChild] > heapArray[largest]) {
largest = rightChild;
}
if (largest != parentIdx) {
swap(&heapArray[parentIdx], &heapArray[largest]);
heapify(heapArray, size, largest);
}
}
// ヒープソートのメイン関数
void heapSort(int* array, int length) {
// 最初に最大ヒープを構築
for (int i = length / 2 - 1; i >= 0; --i) {
heapify(array, length, i);
}
// ヒープから要素を一つずつ取り出し、ソートされた配列を構築
for (int i = length - 1; i > 0; --i) {
swap(&array[0], &array[i]);
heapify(array, i, 0);
}
}
3. 交換ソート
交換ソートの基本的な考え方は、シーケンス内の2つのレコードのキー値を比較し、その結果に基づいて2つのレコードの位置を入れ替えることです。交換ソートの特徴は、キー値が大きいレコードをシーケンスの末尾へ、キー値が小さいレコードをシーケンスの先頭へ移動させることです。
3.1 バブルソート
交換ソートの中で最も一般的なのはバブルソートです。バブルソートは、隣接する要素を比較し、必要に応じて交換を繰り返すことで、より大きい（または小さい）要素を徐々に「浮上」させてシーケンスの末尾へ移動させます。
ここでは、シーケンスが既にソートされている場合、不要な比較をスキップする最適化を加えます。
// 最適化されたバブルソート
void bubbleSort(int* list, int size) {
int swapped;
for (int i = 0; i < size - 1; ++i) {
swapped = 0;
for (int j = 0; j < size - i - 1; ++j) {
if (list[j] > list[j + 1]) {
swap(&list[j], &list[j + 1]);
swapped = 1;
}
}
// このパスで交換が行われなかった場合、配列は既にソートされている
if (!swapped) {
break;
}
}
}
3.2 クイックソート
クイックソートは、1962年にHoareによって提案された、二分探索木構造を利用した交換ソート方法です。その基本的な考え方は、任意の要素（ピボット）を選び、それを基準として配列を2つの部分列に分割します。左部分列のすべての要素はピボットより小さく、右部分列のすべての要素はピボットより大きくなります。その後、左右の部分列に対して同じプロセスを繰り返し、すべての要素が適切な位置に配置されるまで続けます。
クイックソートの再帰は、二分探索木の前順走査に似ています。再帰の深さが n に達し、データ量が大きい場合に「スタックオーバーフロー」が発生する可能性があるため、ピボットの選択に工夫が必要です。ここでは、「三数の中値」法を使用して最適化します。
// 三数の中値を求める関数（ピボットの最適化）
int medianOfThree(int* arr, int left, int right) {
int mid = left + (right - left) / 2;
if (arr[left] > arr[mid]) {
swap(&arr[left], &arr[mid]);
}
if (arr[mid] > arr[right]) {
swap(&arr[mid], &arr[right]);
}
if (arr[left] > arr[mid]) {
swap(&arr[left], &arr[mid]);
}
return mid;
}
// 1. ホアのパーティショニング
int hoarePartition(int* arr, int left, int right) {
int midIdx = medianOfThree(arr, left, right);
swap(&arr[left], &arr[midIdx]);
int pivotValue = arr[left];
int i = left;
int j = right;
while (1) {
while (arr[++i] < pivotValue);
while (arr[--j] > pivotValue);
if (i >= j) break;
swap(&arr[i], &arr[j]);
}
swap(&arr[left], &arr[j]);
return j;
}
// 2. 挖掘法（穴埋め法）のパーティショニング
int holePartition(int* arr, int left, int right) {
int midIdx = medianOfThree(arr, left, right);
swap(&arr[left], &arr[midIdx]);
int pivot = arr[left];
int hole = left;
while (left < right) {
while (left < right && arr[right] >= pivot) --right;
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= pivot) ++left;
arr[hole] = arr[left];
hole = left;
}
arr[hole] = pivot;
return hole;
}
// 3. 前後ポインタ法のパーティショニング
int pointerPartition(int* arr, int left, int right) {
int midIdx = medianOfThree(arr, left, right);
swap(&arr[left], &arr[midIdx]);
int pivotIdx = left;
int prev = left;
int curr = prev + 1;
while (curr <= right) {
if (arr[curr] < arr[pivotIdx] && ++prev != curr) {
swap(&arr[curr], &arr[prev]);
}
++curr;
}
swap(&arr[prev], &arr[pivotIdx]);
return prev;
}
// クイックソート（再帰版）
void quickSortRecursive(int* arr, int left, int right) {
if (left >= right) return;
// int pivot = hoarePartition(arr, left, right);
// int pivot = holePartition(arr, left, right);
int pivot = pointerPartition(arr, left, right);
quickSortRecursive(arr, left, pivot - 1);
quickSortRecursive(arr, pivot + 1, right);
}
// 小さな部分配列に対しては挿入ソートを使用する最適化
void quickSortOptimized(int* arr, int left, int right) {
if (left >= right) return;
if (right - left + 1 > 10) {
// int pivot = hoarePartition(arr, left, right);
// int pivot = holePartition(arr, left, right);
int pivot = pointerPartition(arr, left, right);
quickSortOptimized(arr, left, pivot - 1);
quickSortOptimized(arr, pivot + 1, right);
} else {
// 小さな配列は挿入ソートでソート
for (int i = left + 1; i <= right; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
}
4. マージソート
マージソートは、分割統治法（Divide and Conquer）を用いた効率的なソートアルゴリズムです。まず配列を小さな部分に分割し、各部分をソートしてから、それらをマージ（統合）して完全にソートされた配列を構築します。2つのソート済みリストを1つのソート済みリストに結合する操作を「2-wayマージ」と呼びます。
// マージソートの補助関数
void merge(int* source, int* buffer, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (source[i] <= source[j]) {
buffer[k++] = source[i++];
} else {
buffer[k++] = source[j++];
}
}
while (i <= mid) buffer[k++] = source[i++];
while (j <= right) buffer[k++] = source[j++];
// マージされたデータを元の配列にコピー
for (i = left; i <= right; ++i) {
source[i] = buffer[i];
}
}
// マージソートの再帰部分
void mergeSortRecursive(int* source, int* buffer, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSortRecursive(source, buffer, left, mid);
mergeSortRecursive(source, buffer, mid + 1, right);
merge(source, buffer, left, mid, right);
}
// マージソートのメイン関数
void mergeSort(int* array, int length) {
int* tempBuffer = (int*)malloc(length * sizeof(int));
if (tempBuffer == NULL) {
// メモリ確保失敗の処理
return;
}
mergeSortRecursive(array, tempBuffer, 0, length - 1);
free(tempBuffer);
}
5. 非比較ソート
非比較ソートは、要素同士の比較を行わず、要素の他の特性（例えば値そのもの）を利用してソートします。その中でも、計数ソートは比較的効率的で一般的に使用されます。
計数ソートの基本的な考え方は、各要素の出現回数を数え、その統計情報に基づいて要素を元の配列の「相対的な」位置に戻すことです。これはハッシュの直接アドレス指定法の変形と見なすことができます。
// 計数ソートの実装
void countingSort(int* input, int size) {
if (size <= 1) return;
int minValue = input[0];
int maxValue = input[0];
// 最小値と最大値を見つけ、値の範囲を決定
for (int i = 1; i < size; ++i) {
if (input[i] < minValue) minValue = input[i];
if (input[i] > maxValue) maxValue = input[i];
}
int valueRange = maxValue - minValue + 1;
int* frequency = (int*)calloc(valueRange, sizeof(int));
if (frequency == NULL) {
// メモリ確保失敗の処理
return;
}
// 各値の出現回数をカウント
for (int i = 0; i < size; ++i) {
frequency[input[i] - minValue]++;
}
// frequency配列の情報を使って元の配列を再構築
int outputIdx = 0;
for (int i = 0; i < valueRange; ++i) {
while (frequency[i]-- > 0) {
input[outputIdx++] = i + minValue;
}
}
free(frequency);
}