一般的なソートアルゴリズムについて、それぞれの動作原理と実装例を紹介します。

挿入ソート

挿入ソートは、すでにソート済みの部分列に新しい要素を適切な位置に挿入していく手法です。 具体的には、未処理の各要素を既存のソート済み領域と比較し、正しい場所に配置します。

特性：

1. ほぼソート済みのデータに対して非常に効率的。
2. 時間計算量: O(N^2)。
3. 空間計算量: O(1)。
4. 安定性: 安定。

void InsertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

シェルソート

シェルソートは挿入ソートの改良版で、一定の間隔ごとに要素を比較・入れ替えます。この間隔を徐々に狭めることで、最終的に隣接要素のみを比較する標準的な挿入ソートになります。

特性：

1. 間隔を大きく取ることで全体的な並びを改善し、最終段階での挿入がより高速になる。
2. 時間計算量: ギャップの選択方法により異なるが、通常は O(N^(3/2)) 〜 O(N log N)。

void ShellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

選択ソート

選択ソートは、未処理部分から最小値を見つけ、その要素を先頭に移動させる手法です。

特性：

1. 比較操作が少ないため理解しやすいが、効率は高くない。
2. 時間計算量: O(N^2)。
3. 空間計算量: O(1)。
4. 安定性: 不安定。

void SelectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        std::swap(arr[i], arr[minIdx]);
    }
}

ヒープソート

ヒープソートは二分ヒープを利用したアルゴリズムで、最大（または最小）値を順次取り出してソートします。

特性：

1. 時間計算量: O(N log N)。
2. 空間計算量: O(1)。
3. 安定性: 不安定。

void Heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        Heapify(arr, n, largest);
    }
}

void HeapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; --i) {
        Heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        Heapify(arr, i, 0);
    }
}

クイックソート

クイックソートは「分割統治法」に基づいたアルゴリズムで、ピ벗を中心に左右に分割して再帰的に処理します。

特性：

1. 平均時間計算量: O(N log N)。
2. 最悪の場合: O(N^2)。
3. 安定性: 不安定。

int Partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; ++j) {
        if (arr[j] < pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

マージソート

マージソートは「分割統治法」を用いて、サブリストを再帰的にソートし、それらをマージするアルゴリズムです。

特性：

1. 時間計算量: O(N log N)。
2. 空間計算量: O(N)。
3. 安定性: 安定。

void Merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[m + 1 + j];
    }

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) {
        arr[k++] = L[i++];
    }

    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void MergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        MergeSort(arr, l, m);
        MergeSort(arr, m + 1, r);
        Merge(arr, l, m, r);
    }
}

以上のように、様々なソートアルゴリズムを駆使して配列を昇順に整列できます。