ソートアルゴリズム：挿入ソートとは

ソートアルゴリズムとは

ソートアルゴリズムの意味は、ソートとアルゴリズムの意味を理解すれば分かります。

ソートとは、ある規則に則って、データを並び替えることを指します。

アルゴリズムは、ある課題に対してどのように解決するのかその方法や考え方を指します。

したがって、ソートアルゴリズムとは、バラバラのデータを規則的にどのように並び替えるのかという考え方のことです。

その中の１つである挿入ソートを紹介します。

今回は、バラバラの数値データを昇順に並び替えることを考えます。

挿入ソートとは

一番要素番号が小さい値Aを基準に、一つとなりの値Bを比較します。

要素番号が大きい方Bが小さい方Aより値が小さいと位置を入れ替えます。

Bともう一つとなりの値Cと比較します。

要素番号が大きい方(BorC)が小さい方(AorA,B)より値が小さいと位置を入れ替えます。

この作業を繰り返していきます。

プログラムで書いてみよう

Pythonで挿入ソートと書いてみようと思います。

要素番号が１からリストの長さｎまで繰り返し処理をして、i番目の要素を挿入することを考えます。

隣り合う要素番号の大きい方が小さい方より値が小さい場合、j＝iが代入されます。

jから１ずつ減少して０になるまで、繰り返しを行い、比較しますが、要素番号が大きい方が小さい方より値が大きい場合、順番が決まったので、繰り返しは終了します。

def insert(data):
    n = len(data)
    for i in range(1, n):
        if data[i] < data[i-1]:
            tmp = data[i]
            j = i
            while j > 0:
                data[j] = data[j-1]
                j -= 1
                if tmp >= data[j-1]:
                    break
            data[j] = tmp
    return data

data=[5,4,3,2,1]
print(data)
cdata=insert(data)
print(cdata)

実行結果

[5, 4, 3, 2, 1]
[1, 2, 3, 4, 5]

上手く昇順に並び替えることができたようです。

他にもソートアルゴリズムがあるので、紹介できればと思います。