17/04/21

pythonで挿入ソート


 

今回は挿入ソートを解説、pythonで実装していきます。
挿入ソートはソート済みの配列部分にソートされていない値を挿入するアルゴリズムです。

挿入ソートとは

挿入(インサーション)ソートは「ソート済み部分(前)」と
「未ソートの部分(後)」の2つのデータに分け、
後ろの要素を前部分の適切な場所に挿入する方法です。

手順

  • 未ソートの部分の左端にあるデータを取り出しtempに保存する
  • ソート済みのデータとtempを比較し、ソート済み < tmp だった時ソート済みを右に一つ移動する
  • 移動して空いた位置にtempを挿入する *全てがソート済みになるまで繰り返す

ソースコード

def insertion_sort(li):
    length = len(li);

    for i in range(1,length):
        temp = li[i];
        j = i;

        while j > 0 and li[j-1] > temp:
            li[j] = li[j-1];
            j-=1;

        li[j] = temp

    return li

insertion_sort([3,10,5,1,2]);
# [1, 2, 3, 5, 10]

上記の詳しい説明

ソート済みの値とソートされてないもっとも左端の値とを比較します。

1.ソート済みの"3"とソートされていない"10"を比較します。
"3"< "10"なのでそのままです。
[3,10,5,1,2]
2.ソート済みの"10"とソートされていない要素"5"を比較します。
"10">"5"なので"5"は"3"と"10"の間に挿入します。
[3,5,10,1,2]
3."1"を先頭に挿入します。
[1,3,5,10,2]
4."2"は"1"と"3"の間に挿入します。
[1,2,3,5,10]

以上です。

 

スポンサーリンク

メールアドレスが公開されることはありません。

youya66

だらけとびびり、それとちょっぴりのてきとーさ。

コアラになってだらだらしながら愛されたい。