開発環境とコード規約

本記事で紹介するコードは、C言語標準規格（C99以降）を想定しており、 Visual Studio 2022などの主要な開発環境で動作します。可読性と保守性を向上させるため、変数名は論理的な意味を持つようにリファクタリングし、標準的な型定義を使用しています。

挿入ソート (Insertion Sort)

挿入ソートは、手札のトランプを整理するように、整列済みの部分列に新しい要素を適切な位置に挿入していくアルゴリズムです。データ数が少ない場合や、既にほぼ整列しているデータに対して高速に動作します。

#include <stdio.h>

void insertion_sort(int* arr, size_t n) {
    for (size_t i = 1; i < n; ++i) {
        int key = arr[i];
        size_t j = i;
        
        // 整列済みの部分からkeyより大きい要素を後ろへシフトする
        while (j > 0 && arr[j - 1] > key) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = key;
    }
}

シェルソート (Shell Sort)

シェルソートは、挿入ソートの改良版です。一定の間隔（ギャップ）をおいた要素同士を比較・交換する処理を繰り返し、ギャップを狭めながら最終的に全要素を挿入ソートします。これにより、遠く離れた要素を効率よく移動でき、計算時間を短縮できます。

void shell_sort(int* arr, size_t n) {
    // Knuthの数列を使用した初期ギャップの設定 (gap = gap * 3 + 1)
    for (size_t gap = n / 3; gap > 0; gap /= 3) {
        for (size_t i = gap; i < n; ++i) {
            int temp = arr[i];
            size_t j = i;
            
            // ギャップ幅だけ離れた要素を比較して挿入位置を探す
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

選択ソート (Selection Sort)

選択ソートは、未ソート部分から最小値（または最大値）を見つけ、それを未ソート部分の先頭と交換する操作を繰り返します。安定性はありませんが、実装が単純で、交換回数が少ないという特徴があります。

static void swap(int* x, int* y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void selection_sort(int* arr, size_t n) {
    size_t left = 0;
    size_t right = n - 1;
    
    while (left < right) {
        size_t min_idx = left;
        size_t max_idx = left;
        
        // 範囲内の最小値と最大値のインデックスを探索
        for (size_t i = left + 1; i <= right; ++i) {
            if (arr[i] < arr[min_idx]) min_idx = i;
            if (arr[i] > arr[max_idx]) max_idx = i;
        }
        
        // 最小値を左端に移動
        swap(&arr[left], &arr[min_idx]);
        
        // 最大値が左端にあった場合、交換によって位置がずれているので修正
        if (max_idx == left) max_idx = min_idx;
        
        // 最大値を右端に移動
        swap(&arr[right], &arr[max_idx]);
        
        left++;
        right--;
    }
}

ヒープソート (Heap Sort)

ヒープソートは、配列を二分ヒープとして構築し、そこから最大値（または最小値）を取り出しながら整列を行います。不安定なソートですが、最悪計算量が$O(n \log n)$と保証されており、内部ソートとして優秀です。

static void heapify(int* arr, size_t n, size_t root) {
    size_t largest = root;
    size_t left = 2 * root + 1;
    size_t right = 2 * root + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heap_sort(int* arr, size_t n) {
    // 最大ヒープを構築
    for (int i = n / 2 - 1; i >= 0; --i)
        heapify(arr, n, i);

    // ヒープから最大値を取り出し、配列の末尾に配置
    for (size_t i = n - 1; i > 0; --i) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

バブルソート (Bubble Sort)

隣接する要素を比較し、順序が逆であれば交換することを繰り返します。単純ですが計算効率は低いため、基本的には学習用として使用されます。

void bubble_sort(int* arr, size_t n) {
    for (size_t i = 0; i < n - 1; ++i) {
        int is_swapped = 0;
        for (size_t j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                is_swapped = 1;
            }
        }
        // 1回のパスで交換が発生しなければ整列完了とみなす
        if (!is_swapped) break;
    }
}

クイックソート (Quick Sort)

分割統治法に基づいた高速なソートアルゴリズムです。基準値（ピボット）を選び、それより小さいグループと大きいグループに分割して再帰的にソートします。平均計算量は$O(n \log n)$ですが、最悪の場合は$O(n^2)$となります。

再帰実装（穴掘り法）

ピボットを「穴」として扱い、データを左右にシフトさせながら埋めていく手法です。

#include <stdlib.h>

// 三分割の中央値を取得してピボットの品質を向上させる
size_t get_pivot_index(int* arr, size_t low, size_t high) {
    size_t mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
    if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
    if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
    return mid;
}

size_t partition_hole(int* arr, size_t low, size_t high) {
    size_t pivot_idx = get_pivot_index(arr, low, high);
    swap(&arr[low], &arr[pivot_idx]);
    int pivot = arr[low];
    
    size_t left = low;
    size_t right = high;

    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right]; // 右側の小さい要素を左の穴へ
        
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left]; // 左側の大きい要素を右の穴へ
    }
    
    arr[left] = pivot;
    return left;
}

void quick_sort_recursive(int* arr, size_t low, size_t high) {
    if (low >= high) return;
    if (high - low + 1 < 16) {
        // 小規模な配列は挿入ソートに切り替えて効率化
        insertion_sort(arr + low, high - low + 1);
        return;
    }
    
    size_t pivot = partition_hole(arr, low, high);
    if (pivot > 0) quick_sort_recursive(arr, low, pivot - 1);
    quick_sort_recursive(arr, pivot + 1, high);
}

非再帰実装（スタック利用）

再帰呼び出しによるスタックオーバーフローを防ぐため、自前のスタック構造を用いて実装します。

#include <stdbool.h>

typedef struct {
    size_t* data;
    size_t capacity;
    size_t top;
} Stack;

void stack_init(Stack* s) {
    s->capacity = 64;
    s->data = malloc(sizeof(size_t) * s->capacity);
    s->top = 0;
}

void stack_push(Stack* s, size_t val) {
    if (s->top == s->capacity) {
        s->capacity *= 2;
        s->data = realloc(s->data, sizeof(size_t) * s->capacity);
    }
    s->data[s->top++] = val;
}

size_t stack_pop(Stack* s) { return s->data[--s->top]; }
bool stack_is_empty(Stack* s) { return s->top == 0; }
void stack_free(Stack* s) { free(s->data); }

void quick_sort_iterative(int* arr, size_t n) {
    Stack st;
    stack_init(&st);
    
    stack_push(&st, 0);
    stack_push(&st, n - 1);
    
    while (!stack_is_empty(&st)) {
        size_t high = stack_pop(&st);
        size_t low = stack_pop(&st);
        
        size_t p = partition_hole(arr, low, high);
        
        if (p > 0 && low < p - 1) {
            stack_push(&st, low);
            stack_push(&st, p - 1);
        }
        if (p + 1 < high) {
            stack_push(&st, p + 1);
            stack_push(&st, high);
        }
    }
    stack_free(&st);
}

マージソート (Merge Sort)

配列を分割し、それぞれをソートした後にマージ（統合）するアルゴリズムです。常に$O(n \log n)$の計算量を持ちますが、外部メモリ（一時配列）を必要とします。

#include <string.h>

static void merge(int* arr, size_t left, size_t mid, size_t right, int* temp) {
    size_t i = left;
    size_t j = mid + 1;
    size_t k = 0;
    
    // 2つの配列をマージ
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    // 残りの要素をコピー
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 一時配列から元の配列へコピー
    memcpy(arr + left, temp, sizeof(int) * k);
}

static void merge_sort_helper(int* arr, size_t left, size_t right, int* temp) {
    if (left >= right) return;
    
    size_t mid = left + (right - left) / 2;
    merge_sort_helper(arr, left, mid, temp);
    merge_sort_helper(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

void merge_sort(int* arr, size_t n) {
    int* temp = malloc(sizeof(int) * n);
    if (temp) {
        merge_sort_helper(arr, 0, n - 1, temp);
        free(temp);
    }
}

計数ソート (Counting Sort)

非比較ソートの一種で、データの出現回数を数えて配列の位置を決定します。整数データであり、データの範囲（最大値-最小値）がデータ数に対して十分小さい場合に限り、$O(n+k)$（kはデータ範囲）で非常に高速に動作します。

#include <stdlib.h>

void counting_sort(int* arr, size_t n) {
    if (n == 0) return;

    int min_val = arr[0];
    int max_val = arr[0];
    
    for (size_t i = 1; i < n; ++i) {
        if (arr[i] < min_val) min_val = arr[i];
        if (arr[i] > max_val) max_val = arr[i];
    }
    
    size_t range = max_val - min_val + 1;
    int* count = calloc(range, sizeof(int));
    
    // 各要素の出現回数をカウント
    for (size_t i = 0; i < n; ++i) {
        count[arr[i] - min_val]++;
    }
    
    // カウントに基づいて配列を再構築
    size_t idx = 0;
    for (size_t i = 0; i < range; ++i) {
        while (count[i]-- > 0) {
            arr[idx++] = (int)i + min_val;
        }
    }
    
    free(count);
}