선택 정렬

소개

정렬을 진행하면서 가장 작은 요소, 즉 최솟값을 선택하고 맨 앞으로 배치하는 정렬입니다.
버블 정렬과 마찬가지로 처음부터 끝까지 배열을 탐색하지만 실제로 축적되는 데이터는 제일 앞입니다.

구현

function selectionSort1(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            // SWAP
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

Big-O 복잡도

효율적이지는 않습니다.
배열의 길이가 길어지면 길어질수록 비교 횟수도 n의 제곱 비율로 늘어나게 됩니다.
O(n2) 입니다.
버블 정렬보다 좋을 때가 있는데, 비교를 하고 요소들을 Swap하는 횟수가 적다면 버블 정렬보다 좋습니다.
버블 정렬은 계속해서 Swap하면서 정렬을 진행하기 때문입니다.