経緯
並べ替えアルゴリズムのうち、挿入ソートなるものを見つけ実装しようと思った矢先こんな記事に出会った。
（調べると結構上に出てくる）
- 挿入ソート（基本挿入法）とは未整列の配列から1つずつ値を取り出し整列済み配列の適切な位置へ挿入していく手法です。
- 「6」は「7」より小さくて「5」より大きいので、「5」と「7」の間に挿入
なるほど、新しく配列を用意して、要素を挿入するときは自分で適切な場所を探して挿入するんだな、って解釈した。
ところが、、挿入ソートが自分の実装と異なるものばかりであることが発覚した。
バケットソートでバケツ内の並び替えをするときに、どのアルゴリズムを使うか選択するときに気づいた
myInsert.py
def findInsertIndex(sorted_nums, num):
for i in range(0, len(sorted_nums)):
if num <= sorted_nums[i]:
return i
return len(sorted_nums) + 1
def insertNums(sorted_nums, num):
index = findInsertIndex(sorted_nums, num)
sorted_nums.insert(index, num)
def insertSort(nums):
sorted_nums = [nums[0]]
for i in range(1, len(nums)):
insertNums(sorted_nums, nums[i])
return sorted_nums
Insertion Sort
これを見て気がついた。
みんなの実装とかはこう
Insertion.py
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
それでwikiを調べてみると
- in-placeアルゴリズム
- まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える
- 配列の場合、前の要素を後ろに一つずつずらす
そもそもin-placeなので、新しく配列なんて用意しないし、
挿入ではなく比較しながら並び替えるアルゴリズムだったのがわかった。
自分は何も合っていないじゃあないか。。！
修正後のコード
これでどうだろ
myInsert.py
def insertNums(nums, index):
for j in reversed(range(1, index + 1)):
if nums[j - 1] > nums[j]:
nums[j], nums[j - 1] = nums[j - 1], nums[j]
def insertSort(nums):
for i in range(1, len(nums)):
if nums[i - 1] > nums[i]:
insertNums(nums, i)
return nums
あれは何だったんだ
記事をよくみると
本記事では、"整列済み"と"未整列"の2つに分け"未整列"から1つずつ"整列済み"へ挿入していく挿入ソート（基本挿入法）について図解で分かりやすく解説していきます。
と書いてあるが、これが要約的な意味で言っているなら間違っているとも取れるし、2種類用意してわかりやすく解説しますよなら飲み込める。
自分は前者として解釈してしまった。
終わりに
自分みたくメモリとか速度のことを考慮せず、list型メソッドのinsertとか使ったり、サブルーチン呼び出しまくるコードならまだわかるけどそもそもの実装方針が異なる記事に出会うとは思ってなかった。
なんか批判記事みたいになってしまったけど、自分が勝手に勘違いしてそれを修正した記事です。