Pythonで実装するノームソート：アルゴリズムの仕組みとサンプルコード

この記事では、ノームソート（Gnome Sort）と呼ばれるソートアルゴリズムについて学び、Pythonでの実装方法を解説します。

問題定義

与えられた配列（リスト）を、ノームソートのアルゴリズムを使って昇順に並べ替えることが目標です。

ノームソートは、日常的な動作をモデル化した直感的なアルゴリズムです。庭の植木鉢を並べ替える「ノーム（小人）」の動きに例えられることから、この名前が付きました。バブルソートや挿入ソートに似た考え方に基づいています。

アルゴリズムの手順

1. 配列を左端から右端へ向かって走査する。
2. 現在の要素が前の要素以上であれば、そのまま1つ先へ進む。
3. 現在の要素が前の要素より小さい場合は、2つの要素を交換し、1つ後ろへ戻る。
4. 配列の末尾に到達するまで、上記の手順を繰り返す。

それでは、実際の実装を見ていきましょう。

実装例

def gnomeSort(arr, n):
    index = 0
    while index < n:
        if index == 0:
            index = index + 1
        if arr[index] >= arr[index - 1]:
            index = index + 1
        else:
            arr[index], arr[index-1] = arr[index-1], arr[index]
            index = index - 1
    return arr

# メイン処理
arr = [1,4,2,3,6,5,8,7]
n = len(arr)
arr = gnomeSort(arr, n)
print ("Sorted sequence is:")
for i in arr:
    print (i,end=" ")

実行結果

Sorted sequence is:
1 2 3 4 5 6 7 8

コードのポイント

プログラム内で使用されているすべての変数はローカルスコープで宣言されており、処理の流れは以下のようになっています。

• index変数： 現在注目している要素の位置を表します。最初は0からスタートし、条件に応じて前後に移動します。
• 比較と交換： 前の要素より現在の要素が小さい場合、タプル代入によって2つの要素を効率的に交換し、1つ戻って再度比較を行います。
• 終了条件： indexが配列の長さnに達した時点で、ソート完了となります。

計算量について

ノームソートの時間計算量は、平均および最悪ケースでO(n²)、すでに整列済みのデータに対してはO(n)となります。空間計算量はO(1)で、追加のメモリをほとんど必要としない点が特徴です。

まとめ

この記事では、ノームソートの基本的な仕組みと、Pythonによる実装方法を学びました。コードがシンプルで理解しやすい一方、大規模なデータには不向きであるため、学習用途や小規模データの処理に適したアルゴリズムだと言えます。