[3][알고리즘 - 정렬] 선택정렬(Selection Sort)이란? javascript 구현

선택 정렬(Selection Sort)이란?

 

 

정렬되지 않은 데이터들에 대해

가장 작은 데이터를 찾아

가장 앞의 데이터와 교환해나가는 방식입니다.

 

좀 더 쉽게 표현하면,

각 자리마다 가장 작은 값을 선택하는 개념

이라고 이해하시면 됩니다!!

 

-

출처 - https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

 

생각보다 이해하는데 어렵지 않았던

개념이라 바로 javascript로 구현해보겠습니다.

 

// 랜덤 임의 배열 만들기
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

// 선택 정렬
const selectionSort = (array) => {
    // 각 자리
    for (let i = 0; i < array.length; i++) {
        let minIndex = i;
        // 가장 작은 값 찾기
        for (let j = i + 1; j < array.length; j++) {
            if(array[minIndex] > array[j]) minIndex = j;
        }
        if(minIndex !== i ) [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
    return array;
}


const arr = makeRandomValueArr(10);
console.log('arr=',arr);
// [5, 1, 0, 9, 8, 7, 2, 6, 4, 3]

console.time('selection');
const result = selectionSort(arr);
console.timeEnd('selection');

console.log('result=',result);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

이해가 잘 되셨나요!!?

얼른 정렬을 다양하게 익혀서

시간도 한번 직접 비교해보고 싶네요!!

 

출처 -  https://dev.to/mauriciord/do-you-know-what-is-big-o-notation-1hhp