並べ替えアルゴリズムの基礎
データ構造におけるソート（順序付け）は、ランダムに配置されたデータを特定の規則（昇順または降順）に従って再配列する処理を指します。効率的なデータ管理のためには、適切なソートアルゴリズムの選択が不可欠です。
一般的なソートアルゴリズムの分類
代表的な比較ベースのソート手法には以下のようなものがあります。
- 挿入系
- 直接挿入ソート (Direct Insertion Sort)
- シェルソート (Shell Sort)
- 選択系
- 単純選択ソート (Selection Sort)
- ヒープソート (Heap Sort)
- 交換系
- バブルソート (Bubble Sort)
- クイックソート (Quick Sort)
- その他
- マージソート (Merge Sort)
- 非比較ソート（計数ソート、基数ソート等）
本記事では、C 言語を用いて直接挿入ソートとシェルソートの原理および実装詳細について解説します。
直接挿入ソート (Direct Insertion Sort)
アルゴリズムの原理
この手法は、未整列領域から要素を一つ取り出し、既に整列済みの領域の中から正しい位置を探して挿入するというアプローチを取ります。配列の先頭から 2 番目の要素以降を順次確認し、その要素より前の要素と比較しながら、適切な位置まで移動させます。
実装コード
以下の実装例では、可読性を高めるために変数名を変更し、ロジックを整理しています。
#include <stdio.h>
void performInsertionSort(int *dataSet, int size) {
printf("初期状態：");
for (int idx = 0; idx < size; idx++) {
printf("%d ", dataSet[idx]);
}
printf("\n");
// 2 番目の要素（インデックス 1）から末尾までループ
for (int current = 1; current < size; current++) {
int insertKey = dataSet[current];
int position = current - 1;
// 前面の要素と比較し、insertKey より大きい要素を後ろへずらす
while (position >= 0 && dataSet[position] > insertKey) {
dataSet[position + 1] = dataSet[position];
position--;
}
// 適切な位置に要素を挿入
dataSet[position + 1] = insertKey;
}
}
特性分析
- 時間計算量
- 最良ケース（既に昇順）: O(N)
- 最悪ケース（降順）: O(N²)
- 空間計算量: O(1) （追加のメモリ領域を使用しない）
- 安定性: あり。等しい値の相対的な順序が崩れないため、安定ソートとして機能します。
シェルソート (Shell Sort)
アルゴリズムの原理
シェルソートは直接挿入ソートを拡張したアルゴリズムであり、間隔（gap）を設けて要素同士を比較・挿入を行います。初期段階では大きな間隔でデータを離散させ、大体の並びを整えます。その後、間隔を狭めていくことで最終的に隣接する要素間の比較へと至り、高速な整列を実現します。
間隔が大きすぎる場合は動きが荒くなりすぎ、小さすぎると効率が悪化するため、適切に減衰させていきます（ここでは half-gap 方式を採用）。
実装コード
#include <stdio.h>
void executeShellSort(int *dataSet, int totalElements) {
printf("初期状態：");
for (int i = 0; i < totalElements; i++) {
printf("%d ", dataSet[i]);
}
printf("\n");
// 間隔設定：totalElements の半分ずつ減少させる
for (int gap = totalElements / 2; gap > 0; gap /= 2) {
// ギャップごとのサブ配列に対して挿入ソートを行う
for (int i = gap; i < totalElements; i++) {
int targetVal = dataSet[i];
int j = i;
// 隙間分遡る要素と比較
while (j >= gap && dataSet[j - gap] > targetVal) {
dataSet[j] = dataSet[j - gap];
j -= gap;
}
dataSet[j] = targetVal;
}
// 各ステップの状態出力（デバッグ用）
printf("Gap=%d 時:", gap);
for (int k = 0; k < totalElements; k++) {
printf("%d ", dataSet[k]);
}
printf("\n");
}
}
特性分析
- 時間計算量
- 最良ケース: O(N)
- 最悪ケース: O(N^1.3) 〜 O(N²)（使用するギャップシ퀀スに依存）
- 空間計算量: O(1)
- 安定性: なし。異なる間隔での挿入処理により、同値要素の相対順序が入れ替わる可能性があるため、不安定ソートとなります。
まとめ
直接挿入ソートは小規模なデータセットやほぼ整列済みデータにおいて高い性能を示しますが、大規模データに対してはコストが増大します。一方、シェルソートはこれらを改良し、部分的に整列された状態を作ることで全体の演算量を削減することに成功しています。両者の性質を理解することで、実際のアプリケーション開発において状況に応じたアルゴリズム選定が可能となります。