ノームソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonのノームソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なノームソートを一緒に学習しましょう!

ノームソートとは?

ノームソートは、挿入ソートと非常に似ていて、バブルソートの改良版とも言えます。
非常にシンプルで単純な整列アルゴリズムとも言えます。

ノームソートのアルゴリズムは非常にシンプルです。
下の3ステップでノームソートを実現します。

1.隣接する2つの要素を比較
2.順序が正しければ次の要素を比較、順序が逆であれば入れ替えて前の要素へ移動
3.1〜2を繰り返す

下の動画ではなんとなく、ノームソートをイメージしてみてください。


ノームソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n2O(n2O(n)

ノームソートの計算量は「O(n2)」です。ノームソートは安定ソートといえます。

Pythonコード

def gnome_sort(nums):
    value = 0
    while value < len(nums):
        if value == 0:
            value += 1
        if nums >= nums:
            value += 1
        else:
            nums, nums = nums, nums
            value -= 1
    return nums

上記がPythonを用いて作成したノームソートの関数です。
2行目の「value」はインデックス番号を格納するために宣言しています。

ノームソートの実行例

上記で作成した関数を使用して、実際にノームソートをPython環境で実行してみました。
下記がそのコードと実行結果です。

def gnome_sort(nums):
    value = 0
    while value < len(nums):
        if value == 0:
            value += 1
        if nums >= nums:
            value += 1
        else:
            nums, nums = nums, nums
            value -= 1
    return nums

if __name__ == '__main__':
    nums = [43, 56, 55, 12, 68, 87, 17, 11]
    print(gnome_sort(nums))
【実行結果】
[11, 12, 17, 43, 55, 56, 68, 87]

実行結果から、
14行目で宣言した[43, 56, 55, 12, 68, 87, 17, 11]のリストを昇順に上手くソートできていることがわかります。

ということで、本記事はノームソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です