バブルソート

時間計算量はO(n²)で、追加のメモリ領域を必要としないインプレースソートである。

アルゴリズムの仕組み

隣接する2つの要素を順次比較し、大小関係が逆であれば交換を行う。先頭から末尾まで走査すると、最大値が配列の最後尾に移動する。次に、末尾を除いた範囲で同様の操作を繰り返すことで、未整列部分の最大値が順に後方へ沈んでいく。

実装例

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& data) {
    int n = data.size();
    for (int pass = 0; pass < n - 1; ++pass) {
        bool swapped = false;
        for (int idx = 0; idx < n - pass - 1; ++idx) {
            if (data[idx] > data[idx + 1]) {
                std::swap(data[idx], data[idx + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    std::vector<int> numbers = {4, 3, 6, 7, 23, 765, 87, 5, 46};
    
    std::cout << "Before: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    bubbleSort(numbers);
    
    std::cout << "After: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    return 0;
}

特徴

学習用として最適だが、実用性は低い。アルゴリズム問題で交換回数を求める場合などに限定的に使用される。

選択ソート

時間計算量はO(n²)で、追加メモリを消費しない。

アルゴリズムの仕組み

未整列部分から最小値を見つけ出し、それを未整列部分の先頭と交換する。この操作を全要素に対して繰り返すことで配列を整列させる。

実装例

#include <iostream>
#include <vector>

void selectionSort(std::vector<int>& data) {
    int n = data.size();
    for (int pos = 0; pos < n - 1; ++pos) {
        int minIdx = pos;
        for (int scan = pos + 1; scan < n; ++scan) {
            if (data[scan] < data[minIdx]) {
                minIdx = scan;
            }
        }
        if (minIdx != pos) {
            std::swap(data[pos], data[minIdx]);
        }
    }
}

int main() {
    std::vector<int> numbers = {4, 3, 6, 7, 23, 765, 87, 5, 46};
    
    std::cout << "Before: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    selectionSort(numbers);
    
    std::cout << "After: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    return 0;
}

特徴

配列での実装は安定ソートではない。例えば{2, 5, 5, 9, 1, 4}というデータでは、最初の5が2番目の5より後ろに移動する可能性がある。安定性が必要な場合は連結リストを用いる必要がある。

挿入ソート

時間計算量はO(n²)で、インプレースソートである。

アルゴリズムの仕組み

整列済み部分を維持しながら、未整列部分の先頭要素を適切な位置に挿入していく。新たな要素を整列済み部分の後ろから順に比較し、正しい位置を見つけるまで要素をずらしていく。

実装例

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& data) {
    int n = data.size();
    for (int current = 1; current < n; ++current) {
        int key = data[current];
        int insertPos = current - 1;
        
        while (insertPos >= 0 && data[insertPos] > key) {
            data[insertPos + 1] = data[insertPos];
            --insertPos;
        }
        data[insertPos + 1] = key;
    }
}

int main() {
    std::vector<int> numbers = {4, 3, 6, 7, 23, 765, 87, 5, 46};
    
    std::cout << "Before: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    insertionSort(numbers);
    
    std::cout << "After: ";
    for (int val : numbers) std::cout << val << " ";
    std::cout << "\n";
    
    return 0;
}

特徴

ほぼ整列済みのデータに対しては高速に動作する。小規模データや、他の高度なソートの一部として活用される。

まとめ

これら3つのアルゴリズムはいずれもO(n²)の時間計算量を持つが、動作原理が異なる：

• バブルソート：隣接要素の比較・交換を繰り返し、後方から整列させる
• 選択ソート：最小値を選択して前方に配置し、前方から整列させる
• 挿入ソート：要素を適切位置に挿入し、前方から整列させる