『アルゴリズム4』2.1-選択ソートアルゴリズム(Selection Sort)、Python実装

選択ソートアルゴリズム(Selection Sort)は、ソートアルゴリズムの一次アルゴリズムである.簡単ですが、基礎は、後でより深いアルゴリズムを学ぶのに役立つことを理解しています.小さくないでください.
ソートアルゴリズムの言語の説明:
物体のセットを与え、彼らのある量子化可能な属性に基づいて、大きいものから小さいものまで、または小さいものから大きいものまで並べ替える.例えば、体育の授業を受けるとき、学生たちは身長によって並んでいます.
ソートは簡単な問題のように見えますが、そのコンピュータアルゴリズムには多くのものがあり、性能が異なります.本明細書の選択アルゴリズムは、その1つである.
ソートアルゴリズムの言語記述を選択します.
選択ソートアルゴリズムは、ソートされていない物体のセットから、ある量子化可能な属性に基づいて、まず最小または最大の1つを選択し、最初の位置に置く.そして残りの物体の中から、最小(または最大)のものを選び、2番目の位置に置き、このようにしてすべてが終わるまで押す.
ここでのポイントは、2つの選択問題があり、1つは毎回1つの極値を選択することであり、もう1つは極値が最大か最小かを選択することであるので、選択ソートアルゴリズムと呼ばれています.これは私がこのアルゴリズム名と論理を覚えやすいようにするために、このように理解しています.
学生たちが身長によって並んでいるのを例にとると、初めて、すべての学生の中で一番低い人が持ってきて、最初の学生と位置を変えて、このように最初の位置の学生は一番低いので、動かない.次に、2番目の同級生と彼の後ろの同級生を比較して、一番低いのと2番目の同級生を見つけて位置を変えて、2番目の同級生が一番低いなら動かない.このように推す.
ソートアルゴリズムを選択するコンピュータ言語の説明
1つのN個の数の配列またはリストから、大きいから小さいまでまたは小さいから大きいまでソートするには、次のようにソートします.
1大きい列から小さい列まで押すか、小さい列から大きい列まで押すかを確定します.(ここでは小さい順から大きい順に並べ替えます)
2小さいものから大きいものまで、配列の最初の値は最後に最小値、最後の値は最大値を格納します
3最初の値から開始するか、最後の値から開始するかを決定します.最初の値から始めると、最小値を見つけるたびに、行き先から配列を更新します.最後の値から始めると、最大値を見つけるたびに、後ろから配列を更新します.(以下のアルゴリズムで選択を実現するのは後者である)
4最大値を探すたびに、後で配列を更新すると仮定します.第1ラウンドは、最後の値を他のすべての値と比較し、最大の値を最後の値と交換します.最後の値が最大値であれば、する必要はありません.これにより、配列の最後の値が格納されるのは、配列全体の最大値です.
5第2ラウンドは、最後から2番目の値を前のすべての値と比較し、最大値と最後から2番目の値を交換します.
6は、2番目と1番目の値が比較されるまで、このようにします.
選択ソートアルゴリズムの実装
ここではPythonを使っています(Java実装はSelection.javaを参照)
選んだのは、毎回最大値を探して、後ろから前列に向かいます.古典的な選択ソートアルゴリズムとは少し異なり(最小値法)、自分に難易度を上げて直接答えを見るのを避けるためです.
アルゴリズム実装コード(selection_sort.py):

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

class SelectionSort(object):
    items=[]
    def __init__(self,items):
        self.items = items

    def sort(self):
        print "iten len: %d" % len(self.items)
        for i in range(len(self.items)-1,0,-1):
            maximum = i
            for j in range(0,i):            
                if (self.items[i] < self.items[j]):
                    maximum = j
            self.items[i],self.items[maximum]=self.swap(self.items[i],self.items[maximum])
    def swap(self,i,j):
        temp = j
        j = i
        i = temp
        return i,j

テストコード:

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

from selection_sort import SelectionSort

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

ssort = SelectionSort(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 selection sort method - %ds, python builtin sort - %ds" % (duration1, duration2)

テストコードでは、pythonが独自のsortメソッドを使用して、「assert ssort.items==items」という文を使用して、選択ソートアルゴリズムの実行結果の正確性を検証します.さらにtimerを加えて,我々のアルゴリズムとpythonが持参したsort法の実行時間を比較した.
実行結果は、ソートの結果は同じであることを示していますが、私たちのアルゴリズムは配列が大きい場合、例えば配列sizeが4000前後で、1 s以上かかりますが、pythonが持っているアルゴリズムは超速く、ミリ秒レベルです.データが10000になると、私たちのアルゴリズムは5 s以上実行されますが、pythonが持っているsortメソッドは1 s未満です.これは、ソートアルゴリズムの選択が簡単であるが、パフォーマンスが悪いことを示している.
実行結果の例(配列size=10):

----------sorting numbers__________
original items: [434, 706, 256, 95, 549, 380, 585, 535, 722, 689]
iten len: 10
sorted items: [95, 256, 380, 434, 535, 549, 585, 689, 706, 722]
Duration: our selection sort method - 0s, python builtin sort - 0s

文字列のソートについては、テストコードと実行結果も一緒に載せます.

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

print "-"*10 + "sorting alpha characters" + "_"*10
items=[]
for i in range(0,10):
    items.append(random.choice(string.ascii_letters))
print "original items: %r" % items
ssort = SelectionSort(items)
ssort.sort()
items.sort()
assert ssort.items == items
print "sorted items: %r" % ssort.items

print "-"*10 + "sorting strings" + "_"*10
items=[]
for i in range(0,10):
    items.append("".join(random.choice(string.ascii_letters+string.digits) for s in range(0,10) ))
print "original items: %r" % items
ssort = SelectionSort(items)
ssort.sort()
items.sort()
assert ssort.items == items
print "sorted items: %r" % ssort.items

実行コード:

----------sorting alpha characters__________
original items: ['m', 'q', 'a', 'c', 'n', 'w', 'V', 'f', 'a', 'p']
iten len: 10
sorted items: ['V', 'a', 'a', 'c', 'f', 'm', 'n', 'p', 'q', 'w']
----------sorting strings__________
original items: ['QSvTmfkUAX', 'uf2dEtEtlk', 'lzyYWD3w59', '3pCKM10RPK', 'ARDf403rrl', 'dZyirpxn2N', 'picoZ7yvhR', 'VU9aW1PSbt', 'YvwqwzO39r', 'ROxlks3zAl']
iten len: 10
sorted items: ['3pCKM10RPK', 'ARDf403rrl', 'QSvTmfkUAX', 'ROxlks3zAl', 'VU9aW1PSbt', 'YvwqwzO39r', 'dZyirpxn2N', 'lzyYWD3w59', 'picoZ7yvhR', 'uf2dEtEtlk']

ソートアルゴリズム解析の選択
前のアルゴリズムで実現した例により,ソートアルゴリズムの選択に性能問題があった.
アルゴリズムで使用した比較回数と値交換回数で分析してみます.
一番目の最大値を探す時、N-1回を比較する必要があり、一番目の最大値を交換する時、N-2回を比較する必要があり、一番最後の値を交換する時、1回比較する必要があり、1回交換する必要がある
だから、全部で1+2+...+(N−1)次=(Nの二乗)/2次であり,その複雑さはもはや線形ではない.総交換回数はN回で、相対的にいいです.
選択ソートアルゴリズムを改善するには、どうすればいいか考えてみましょう.