ノームソートのC++プログラム：仕組みと実装例をわかりやすく解説

ノームソート（Gnome Sort）は、挿入ソートによく似たソーティングアルゴリズムの一つです。ただし、要素を本来あるべき位置へ移動させる方法として、バブルソートと同じように「隣接する要素の一連の交換（スワップ）」を用いる点が特徴となっています。

入力: 53421
出力: 12345

アルゴリズムの解説

ノームソートでは、隣接する2つの要素を比較し、順序が崩れている場合にはそれらを交換しながら、各要素を徐々に正しい位置へ移動させていきます。複雑なデータ構造や再帰処理を必要とせず、単純なループだけで実装できるシンプルさが魅力のアルゴリズムです。

動作の流れ

• 先頭から順に、隣り合う2つの要素を比較します。
• 順序が正しければ、インデックスを1つ先へ進めます。
• 順序が誤っていれば、2つの要素を交換し、インデックスを1つ後ろへ戻します。
• これを配列全体が昇順に整列されるまで繰り返します。

最悪時・平均時の計算量は O(n²)、すでに整列済みのデータに対しては O(n) と効率よく動作します。小規模なデータや学習用途に適したアルゴリズムと言えるでしょう。

C++による実装例

#include <iostream>
using namespace std;
int main() {
    int temp;
    int arr[] = { 5, 3, 4, 2, 1 };
    int n = 5;
    int i;
    i = 0;
    while (i < n) {
        if (i == 0 || arr[i - 1] <= arr[i])
            i++;
        else {
            temp = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = temp;
            i = i - 1;
        }
    }
    for (i = 0; i < n; i++) {
        cout << arr[i] << "\t";
    }
}

このプログラムを実行すると、配列 {5, 3, 4, 2, 1} が昇順に並べ替えられ、「1 2 3 4 5」と出力されます。コードの構造が非常に単純なので、ソートアルゴリズムの入門としても理解しやすいのがポイントです。