データ構造とアルゴリズム：gnome sort（ノームソート）

重要度：低い

Bubbleソートと類似のソート手法で、左から順にみていき入れ替えた時にBubbleソートはそのまま右にずれるが、ノームソートでは入れ替えた後は左にずれる。

順番が正しい場合はスキップ

順番が正しくない場合はスイッチする。この後バブルソートでは右側に移動するがノームソートではスイッチした後に左側にずれるように動く。

そうすると2,1を比べた時に一番左側に2があるのでここもスイッチする。それ以上左にいけなくなったら再度右移動に戻って同じことを繰り返していく。

右側に行って、7,8を比べた時に順番が逆なので、入れ替える。その後、一度左に行って、5,7を比べた時に順番が正しいので右に進む。左側に小さい数を貯めていく方式なので、一度左に行って正しければそれ以上左に戻る必要はない。

右に大きい数字があったら正しい位置に配置されるまで左に向かい数値をスイッチしていき、右に一つもどって確認して一番右までスイッチがなく終了したらソートが完了する。

from typing import List
import random

def gnome_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    index = 0
    while index < len_numbers:
        if index == 0:
            index += 1
        if numbers[index] >= numbers[index-1]:
            index += 1
        else:
            numbers[index], numbers[index-1] = numbers[index-1], numbers[index]
            index -= - 1
    return  numbers

numbers = [random.randint(0,1000) for i in range(10)]
print(gnome_sort(numbers))

[87, 537, 811, 379, 306, 230, 853, 263, 861, 923]