『アルゴリズム4』2.1-挿入ソートアルゴリズム(Insertion Sort)、Python実装

ソートアルゴリズムリストエレベーター:

選択ソートアルゴリズム:詳細はSelection Sort

を参照

挿入ソートアルゴリズム(Insertion Sort):小さな配列と部分的にソートされた配列に非常に適しており、比較的多くのアルゴリズムが適用されています.詳細は本論文

参照
ソートアルゴリズムの言語記述を挿入します.
みんなトランプをしたことがあるでしょう.トランプをするとき、一人一人が手にトランプを持っています.普通は大きい順に並べて、新しいトランプ(例えば5)を捕まえるたびに、4と6を見つけて、6を後ろにずらして、5を4と6の間に差し込みます.
ソートアルゴリズムを挿入する原理は理札と同じで、ソートされていない物体や部分的にソートされている物体のグループの中で、物体を左から右に1つずつ比較し、比較するたびに、物体を小さいものから大きいものに並べ、比較するたびに、前のいくつかの物体は順番に並べられ、後ろの物体は前に並べられたシーケンスに挿入され、このようにすべてのソートが完了するまでプッシュされます.
ここで重要なのは,前に並べられた配列に後ろの物体を挿入することであるので,挿入ソートと呼ぶ.
ソートアルゴリズムを挿入するコンピュータ言語の説明
1つのN個の数の配列またはリストから、大きいから小さいまでまたは小さいから大きいまでソートするには、次のようにソートします.
1大きい列から小さい列まで押すか、小さい列から大きい列まで押すかを確定します.(ここでは小さい順から大きい順に並べ替えます)
2小さいときから大きいときは、2番目を1番目と比較し、1番目より小さい場合は1番目と位置を交換します.逆は変わらない.
4 3つ目を前の2つとそれぞれ比較し、小さい場合は挿入します.
6このようにして、最後の1つまで押します.
注意したいのは、挿入するときは、配列の挿入される部位の値を後ろにずらす必要がありますよ.
ソートアルゴリズムの実装の挿入
ここではPythonを使っています.
最初は挿入の概念を際立たせるために、愚かな方法を使って、配列値を一歩ずらして挿入しました.後でより簡潔なコードが与えられます.
アルゴリズム実装コード(insertion_sort.py):

# -*- coding: utf-8 -*-

class InsertionSort(object):
    items = []
    def __init__(self,items):
        self.items = items
    def sort(self):
        for i in range(0,len(self.items)-1):
            temp = self.items[i]
            if (self.items[i] < self.items[i-1]):
                for j in range(0,i):
                    if (self.items[j] > temp):
                        for k in range (i,j,-1):
                            self.items[k] = self.items[k-1]
                        self.items[j] = temp
                        break;

上のコードは挿入がどのように機能しているかをはっきり見ることができますが、確かに馬鹿で、以下のように簡略化することができます.

class InsertionSort_Refined(object):
    items = []
    def __init__(self,items):
        self.items = items
    def sort(self):
        for i in range(0,len(self.items)-1):
            j = i;
            while (j > 0 and self.items[j] < self.items[j-1]):
                self.items[j],self.items[j-1] = self.swap(self.items[j],self.items[j-1])
                j -=1
    def swap(self,i,j):
        temp = j
        j = i
        i = temp
        return i,j

テストコード:

# -*- coding: utf-8 -*-
import random
from timeit import default_timer as timer

from insertion_sort import InsertionSort

print "-"*10 + "sorting numbers" + "_"*10
items = []
for i in range(0,10):
    items.append(random.randint(2,999))
print "original items: %r" % items
ssort = InsertionSort(items)

# calculate execution time for our selection sort method
start = timer()
ssort.sort()
end = timer()
duration1 = end - start
# calculate execution time for python built-in sort method
start = timer()
items.sort()
end = timer()
duration2 = end - start

assert ssort.items == items
print "sorted items: %r" % ssort.items
print "Duration: our insertion sort method - %ds, python builtin sort - %ds" % (duration1, duration2)

テストコードでは、pythonが独自のsortメソッドを使用して、「assert ssort.items==items」という文を使用して、挿入ソートアルゴリズムの実行結果の正確性を検証します.さらにtimerを加えて,我々のアルゴリズムとpythonが持参したsort法の実行時間を比較した.
実行結果は,ソートの結果は同じであり,選択ソートアルゴリズムとは差が少なく,データ量が大きい場合,pythonが持参したsortアルゴリズムよりも実行性能が劣ることを示した.
実行結果の例(配列size=10):

----------sorting numbers__________
original items: [420, 373, 678, 818, 264, 30, 150, 310, 101, 833]
sorted items: [30, 101, 150, 264, 310, 373, 420, 678, 818, 833]
Duration: our insertion sort method - 0s, python builtin sort - 0s

ソートアルゴリズム解析の挿入
前述のアルゴリズムで実現した例により,挿入ソートアルゴリズムにも性能問題がある.
アルゴリズムで使用した比較回数と値交換回数で分析してみます.
2番目と1番目を比較する場合、1回、1回、3回交換する場合、2回比較する必要がある場合、2回交換して最後の値を探す場合、N-1回比較する必要がある場合、N-1回交換する必要がある場合、N-1回交換する必要がある場合があります
だから、最悪の場合、全部で1+2+...+(N−1)回＝(Nの二乗)／2回、比較回数も1＋2＋…＋(N−1)回＝(Nの二乗)／2回.その複雑さはもう線形ではない.
しかし、配列が既にソートされている場合、N−1回の比較のみが必要であり、交換は不要であることが望ましい.
したがって、配列がすでに部分的または全部並べ替えられている場合は、挿入並べ替えアルゴリズムを使用するのは間違いなく良い選択です.