1. バブルソート

1.1 基本的なバブルソート

バブルソートは最も単純なソートアルゴリズムの一つです。隣り合う要素を比較し、大きい方を右に移動させることで昇順に並べます。以下の例を見てみましょう。 配列 [5, 1, 4, 2, 8, 4] をバブルソートを使って並べ替えてみます。異なる値の4を区別するために色分けしています。

• ステップ1: 5 と 1 を比較して、5 > 1 のため交換。
• ステップ2: 5 と 4 を比較して、5 > 4 のため交換。
• ステップ3: 5 と 2 を比較して、5 > 2 のため交換。
• ステップ4: 5 と 8 を比較して、5 < 8 のため交換しない。
• ステップ5: 8 と 4 を比較して、8 > 4 のため交換。

最初のラウンドが終了すると、最大値である8が最後尾に移動します。

1.1.1 基本的なバブルソートのコード実装

void basicBubbleSort(SortArray *array) {
    for (int i = 0; i < array->size - 1; ++i) {
        for (int j = 0; j < array->size - 1 - i; ++j) {
            if (array->elements[j] > array->elements[j + 1]) {
                swapItems(&array->elements[j], &array->elements[j + 1]);
            }
        }
    }
}

1.2 最適化されたバブルソート

このアルゴリズムを改良し、配列が既にソート済みの場合に無駄な操作を省くことができます。`isSorted` フラグを使用して、交換がない場合に処理を終了します。

1.2.1 最適化されたバブルソートのコード実装

void optimizedBubbleSort(SortArray *array) {
    for (int i = 0; i < array->size - 1; ++i) {
        bool isSorted = true;
        for (int j = 0; j < array->size - 1 - i; ++j) {
            if (array->elements[j] > array->elements[j + 1]) {
                swapItems(&array->elements[j], &array->elements[j + 1]);
                isSorted = false;
            }
        }
        if (isSorted) break;
    }
}

1.3 さらなる最適化

最後の交換位置を記録することで、不要な比較をさらに削減できます。

1.3.1 さらなる最適化のコード実装

void furtherOptimizedBubbleSort(SortArray *array) {
    int lastSwapIndex = array->size - 1;
    while (lastSwapIndex > 0) {
        int newSwapIndex = 0;
        for (int i = 0; i < lastSwapIndex; ++i) {
            if (array->elements[i] > array->elements[i + 1]) {
                swapItems(&array->elements[i], &array->elements[i + 1]);
                newSwapIndex = i;
            }
        }
        lastSwapIndex = newSwapIndex;
    }
}

2. クイックソート

クイックソートは分割統治法に基づいた効率的なソートアルゴリズムです。基準値（ピボット）を設定し、その値より小さいものを左に、大きいものを右に配置します。その後、再帰的に左右の部分をソートします。

2.1 両側ループ法

左右のポインタを使い、互いに向かって進んでいきます。ピボットより小さい値は左に、大きい値は右に移動させます。

2.1.1 両側ループ法のコード実装

int partitionDual(SortArray *array, int start, int end) {
    int pivot = start;
    int left = start, right = end;

    while (left < right) {
        while (left < right && array->elements[right] >= array->elements[pivot]) --right;
        while (left < right && array->elements[left] <= array->elements[pivot]) ++left;
        if (left < right) swapItems(&array->elements[left], &array->elements[right]);
    }

    swapItems(&array->elements[pivot], &array->elements[left]);
    return left;
}

void quickSortDual(SortArray *array, int start, int end) {
    if (start >= end) return;
    int pivot = partitionDual(array, start, end);
    quickSortDual(array, start, pivot - 1);
    quickSortDual(array, pivot + 1, end);
}

2.2 単一ループ法

一方のポインタのみを使用し、ピボットより小さい値を見つけたときにマーカーを更新します。

2.2.1 単一ループ法のコード実装

int partitionSingle(SortArray *array, int start, int end) {
    int pivotValue = array->elements[start];
    int mark = start;

    for (int i = start + 1; i <= end; ++i) {
        if (array->elements[i] < pivotValue) {
            ++mark;
            swapItems(&array->elements[mark], &array->elements[i]);
        }
    }

    swapItems(&array->elements[start], &array->elements[mark]);
    return mark;
}

void quickSortSingle(SortArray *array, int start, int end) {
    if (start >= end) return;
    int pivot = partitionSingle(array, start, end);
    quickSortSingle(array, start, pivot - 1);
    quickSortSingle(array, pivot + 1, end);
}