Prologue

Sortingを学習する過程で、どのような状況で何を書くべきかを理解し、より大きなアルゴリズムを作成する際に役立つことを望んで、いくつかの点をまとめてみました.だから私たちが知っているのは大体3点です.

アルゴリズム

実施

best and worst case

そしてこれは私たちが後で並べ替える配列です.

Building block

selection sortは、arrayから最小の数を選択して先頭に送信し、次いで2番目の小さい数を選択して2番目の位置に送信する方法によって動作する.
arrayで最小の数を探して、最初はどこにあるか分からなかったので、一番前の数を選んで、順番に比較します.

1が4より小さいので、最小の数を1に変更し、後の数字と順に比較します.





比較結果は,1がarrayで最小の数であるため,1と4の位置が変化することを示した.

今では1回目のループが終わりました.arrayが整列するまで繰り返します.

Think visually

前にarrayで最小の数を見つけて、一番左に置いた.だから同じ仕事は2番目のインデックスから始めればいいのです.

4を選択して右の数字と比較します.

最小の数は2です.

2番目のループでは、1番目に選択された4と位置が入れ替わる.
このときのポイントは、最初に一番小さいと思っていた数字と、選んだ数字を忘れないことです.このようにして、後ろの最小の数字が現れたときに最初に思いついた数字の位置に変えることができます.

Pseudo code

1. array의 index를 다 돌때가지 반복
2. index 순서대로 가장 작은 수로 지정
3. 2에서 정한 index이후부터 남은 index까지 반복
4. index 순서대로 2에서 정한 값과 비교
4-1. 2의 값보다 4의 값이 작으면
4-2. 가장 작은 값의 index 교체
5. 3번 loop 종료
6. 3과 4-2가 다르면
7. 4-2의 수와 2의 수 교체
8. 1번 loop 종료

Implementation

def selection_sort(array):
    for i in range(len(array)-1):   
        lowest = i
        for j in range(i+1, len(array)):
            if array[lowest] > array[j]:
                lowest = j
        if lowest != i:
            array[i], array[lowest] = array[lowest], array[i]

    return array

Best and worst case

selection sortもbubble sortのように比較・交換される.しかし、bubble sortとは異なり、loopごとに1回の交換しか発生しない.

最適:配列の整列
n(‖1)/2 n(n-1)/2 n(‖1)/2回は比較のみ発生する.

最悪:逆順配列
比較はn(n−1)/2 n(n−1)/2 n(n−1)/2回,交換(n−1)(n−1)回発生した.

Epilogue

selection sortとbubble sortの間に1つ書く場合は、selection sortと書きます.2つのアルゴリズムの最悪の状況を比較すると,はっきり見える.

bubble sort: n2n^2n2

selection sort: (n+2)(n−1)/2(n+2)(n-1)/2(n+2)(n−1)/2

二次項がすべて取り除かれると、n 2 n^2 n 2とn 2/2 n^2/2 n 2/2の間に何を書くかという問題と同じように、selection sortはbubble sortより2倍速い.