C++で学ぶノームソート（Gnome Sort）の仕組みと実装方法

この記事では、ノームソート（Gnome Sort）の動作原理について詳しく解説します。ノームソートはシンプルなソートアルゴリズムの一つで、「ノーム（庭の小人）が鉢植えの花を並べ替える様子」から名付けられたと言われています。

このアルゴリズムの大きな特徴は、リストがすでにソート済みである場合に O(n) の時間で処理が完了する点です。つまり、最良ケースの計算量は O(n) となります。一方、平均ケースおよび最悪ケースの計算量は O(n²) であり、バブルソートと同程度の性能になります。

ノームソートのアルゴリズム

gnomeSort(arr, n)

begin
    index := 0
    while index < n, do
        if index is 0, then
            index := index + 1
        end if
        if arr[index] >= arr[index -1], then
            index := index + 1
        else
            exchange arr[index] and arr[index - 1]
            index := index - 1
        end if
    done
end

アルゴリズムの流れ

ノームソートの基本的な考え方は以下の通りです。

• 先頭から順に隣り合う要素を比較します。
• 現在の要素が前の要素以上であれば、そのまま次へ進みます（index を +1）。
• 順序が逆転していれば、2つの要素を交換し、index を -1 して前に戻ります。
• これを配列の末尾まで繰り返すことで、全体が昇順に整列されます。

C++による実装例

それでは、実際にC++でノームソートを実装してみましょう。

#include<iostream>
using namespace std;

void gnomeSort(int arr[], int n){
    int index = 0;
    while(index < n){
        if(index == 0) index++;
        if(arr[index] >= arr[index - 1]){ // 前の要素より大きい場合はそのまま進む
            index++;
        } else {
            swap(arr[index], arr[index - 1]); // 順序が逆なら交換
            index--; // 一つ戻って再度チェック
        }
    }
}

main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    gnomeSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

実行結果

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

まとめ

ノームソートは挿入ソートに似た動作をする直感的なアルゴリズムです。実装が非常に簡単で、ほぼ整列されたデータに対しては高速に動作するため、学習用途や小規模データの整列に適しています。ただし、計算量が O(n²) となるため、大規模なデータセットにはクイックソートやマージソートなど、より効率的なアルゴリズムを選択することをおすすめします。