선택 정렬, Selection Sort

침대위의 양갱. 투머치 클로즈업.

입력 : 같은 타입의 변수를 가진 배열

출력 : 해당 타입의 오름차순 / 내림차순에 따른 정렬된 배열

빅오 표기법 : O(n^2)

 

*빅오 표기법에 대해.

O(n) : 모든 원소를 한 번씩 건드려야 한다는 뜻. 

예) 가수 목록에서 가수를 찾아보자.  이 중 가장 연주 횟수가 가장 많은 가수를 찾기 위해선 모든 항목을 점검해야함. 

-> 모든 항목을 점검하므로 O(n), 이를 n번 반복해서 목록을 정렬해야함. => O(n)

 

#javascript

var list = [3,55,1,33, 44, 20, 9, 7, 15, 49];
console.log("Before Selection Sort : " + list);
console.log("After Selection Sort : ");
console.log(selectionSort(list));

function findSmallest(_list)
{
    var min = _list[0];
    
    for(var i = 0 ; i < _list.length ; ++i)
    {
        if(min > _list[i])
            min = _list[i];
    }
    return min;
}

function selectionSort(_list)
{
    
    var ascList = [];
    var smallest = -1;
    var len = _list.length;
    
    for(var i = 0 ; i < len ; ++i)
    {
        smallest = findSmallest(_list);
        var idx = _list.indexOf(smallest);
        ascList.push(_list[idx]);
        _list.splice(idx, 1);
        
    }
    console.log(ascList);
}

 

선택정렬은 깔끔한 알고리즘이지만 빠르진 않음.