【アルゴリズム(JS実装)】Selection Sort

 　どうも、わくばです！

　今日はSelection Sort を学びました。今回はシンプルです。

　アルゴリズムの説明はこのサイトが非常にわかりやすいのでぜひ：Selection Sort - InterviewBit

　コードはこんな感じになりました。

function selectionSort(array, size){
    const { length } = array;
    for (let i=0; i< length; i++){
        let minIdx = i;
        for(let j =i+1; j < length; j++){
            if(array[i]>array[j]){
                minIdx = j;
            }
        }
        [array[i], array[minIdx]] = [array[minIdx], array[i]];
    }
    return array;
}

 　実行してみると 

let data = [-2, 45, 0, 11, -9]
selectionSort(data, data.length)

[-9, -2, 0, 11, 45]

 　機能しています。

Complexityはスワップし終えたものは比較対象から減っていくので

$$(n-1)+(n-2)+...+2+1=\dfrac{n(n-2)}{2}$$

これは概算すると\(O(n^2)\)になります。ループが二重なので直感的にも納得です。(Big O notationを知らない方のために一応コメントしておくと、Big O notationはあくまで複雑性の指標であって正確な計算値ではありません。処理の複雑さ的に\(O(n^2)\)とすると定性的に理解できて良いですね、というものです。)

今日は以上です。E資格の勉強引き続き頑張ります。あ、あと医学も！(笑)

では。