[javascript] 선택정렬

공부하기 싫어서 그런가 갑작스럽게 선택정렬 포스팅을 하고 싶어졌다. 

 

분석

선택정렬은 만들기는 쉬우나, 이동과 비교가 많아 O(ne2)의 복잡도를 가지는 정렬이다. 단순한 정렬 방법으로, 정렬되지 않은 배열에서 처음 부터 끝까지 돌며 가장 작은 수를 골라 정렬된 배열의 끝에 삽입한다. 

 

타언어는 배열의 중간에 있는 것을 삭제하는 작업이 매우 귀찮은데, 자바스크립트는 splice 메서드를 제공해주어 비교적 쉽게 삭제가 가능합니다. 

 

코드

 

//임의의 길이의 랜덤한 값이 들어있는 배열을 반환하는 함수
function makeArray(){
    let randomIndex = Math.floor(Math.random() * 100);

    const array = [];

    for(let i = 0; i<randomIndex; i++){
        let randomValue = Math.floor(Math.random() * 100);
        array[i] = randomValue;
    }
    
    return array;
}

function selectionSort(array){
    let tempLength = array.length;
    const sortedArray = [];
    for(let i = 0; i < tempLength; tempLength--){
        let minimum = array[0];
        let cutLocation = 0;
        for(let u = 0; u < tempLength; u++){
            if(minimum > array[u]){
                minimum = array[u]
                cutLocation = u;
            }
        }
        //정렬되지 않은 배열에서 가장 작은 수가 있는 버킷 삭제 
        array.splice(cutLocation,1);
        
        sortedArray.push(minimum);
    }
    console.log(sortedArray);
}

const array = makeArray();
selectionSort(array);