挿入ソートについて
- 始めに先頭の要素はソート済みとする
- 2つ目の要素から順に並べ替えを行い、ソート済みとしていく
- ソート対象の要素に対して、ソート済みの要素を後ろから順に大小比較して並べ替え先を調べる
- 並べ替え先がわかれば、その場所にソート対象の要素を代入するため、ソート済みの要素を後ろから順に1つずつ右にずらしていく
- ソート済みの要素のうち、右端の要素を1つ右にずらすと、ソート対象の要素が上書きされてしまうため、ソート対象の要素は一時的に別の変数に保存しておく
- ソートすべき位置にソート対象の要素を代入する
- 計算量はO(n^2)、一度も交換が発生しない場合はO(n)
コード
|
1 2 3 4 5 6 7 8 9 10 11 |
data = [1,5,3,2,8,9,10,6,7,4] for i in range(1, len(data)): #先頭はソート済みとするので1から開始 temp = data[i] #[1]ソート対象の要素を一時的に保存 j = i-1 #[2]最後にソート済みとなった要素のインデックスをjに代入 while(j>=0) and (data[j]>temp): #[3]jが0以上かつ最後にソートされた要素がソート対象の要素より大きい場合 data[j+1]=data[j] #[4]ソート済みの要素のうち、右端の要素を1つ右にずらす j-=1 #[5]ソート済みの要素を後ろから順に右に1つずつずらすため、インデックスを1つ減らす data[j+1]=temp #[6]ソート位置にtempに保存していたソート対象の要素を代入する print(data) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
ソート対象の要素とは、ソート済みの要素のうち、右端にある要素の次の要素になります。
例)：[1,5,3,2]のリストがあり、3をソートする場合
ソート対象であるdata[2]=3はtempに一時的に保存します。[1]
1,5がソート済です。ソート済要素のうち、右端の要素は5ですが、その次の要素はソート対象である3です。
最後にソートされたのは5であり、そのインデックスである1をjに代入します。[2]
data[j]=data[1]は5ですが、tempに保存されている3よりも大きく、j=1は0よりも大きいためwhile節で並べ替えが発生します。[3]
while節の中では、1と5の間に3を代入するため、5を1つ右にずらします。具体的には、data[j+1]=data[2]、つまり現在3がある位置に5を代入します。[4]
例)：[1,5,3,2]→[1,5,5,2]
この時、そのままずらしてしまうとソート対象である3が上書きされてしまいました。
上書きされてしまいましたが、3は事前に”temp”に保存しています。[1]
3のソート先の場所であるdata[j+1]=data[1]に対して、tempに保存していた3を代入します。[6]
例)：[1,5,5,2]→[1,3,5,2]
これで、1,3,5まではソート済みとなったので、for節の次のループに入り、2がソート対象となります。以降はこの繰り返しになります。
参考
こちらの書籍を参考にしています。
初めてアルゴリズムを勉強する人を対象に書かれた本だと思います。
知らない分野について勉強するときはわからないことや理解できないことが連続するので、集中して勉強を続けることができず辛いことが多いですが、そんな私のような初学者でも続けられるように、重たくならない内容で説明されています。
コメント