[24] 선택 정렬(Selection Sort)

* 주의! 독학한 내용이므로 틀린 내용은 댓글로 남겨주세요!

 

배열을 한 번 훑을 때 최소값을 찾아서 맨 앞으로 보낸다.

다시 훑을 때는 두 번째 요소부터 훑으며 최소값을 두 번째 요소 자리로 보낸다.

이걸 (배열의 길이 - 1) 만큼 반복한다.

 

장점: 버블 정렬보다 항상 빠르다!(그리고 쉽다!)

단점: 역시 느리다!(시간복잡도가 버블 정렬과 마찬가지로 O(n^2)이다!)

 

이중선택정렬도 있다.

한 번 훑을 때 최소값과 최대값을 찾아서 맨 앞과 맨 뒤로 보낸다.

다시 훑을 때는 두 번째 요소부터, 끝에서 두 번째 요소까지 훑으며 최소값과 최대값을 움직인다.

이걸 (배열의 길이 / 2) 만큼 반복한다.

 

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

선택 정렬 - 위키백과, 우리 모두의 백과사전

 

프로그래머스 > 코딩테스트 > 해시 > 완주하지 못한 선수

 

Selection Sort로 풀어보기!

function selectionSort(array) {
    for (let i = 0; i < array.length; i++) {
        let max = i;

        for (let j = i + 1; j < array.length; j++) {
            if (array[max] > array[j]) max = j;
        }

        if (max !== i) {
            const temp = array[max];
            array[max] = array[i];
            array[i] = temp;    
        }
    }
}

function solution(participant, completion) {
    selectionSort(participant);
    selectionSort(completion);

    for (let i = 0; i < completion.length; i++) {
        if(participant[i] !== completion[i]) return participant[i];
    }
    return participant.pop();
}

정확성 테스트

테스트 1 〉	통과 (0.12ms, 29.9MB)
테스트 2 〉	통과 (0.13ms, 29.9MB)
테스트 3 〉	통과 (31.97ms, 32.5MB)
테스트 4 〉	통과 (37.30ms, 32.6MB)
테스트 5 〉	통과 (12.67ms, 32.6MB)

 

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

 

결과: 시간 초과! ㅠㅠ

 

 

DoubleSelectionSort로 풀어보기!

function doubleSelectionSort(array) {
    let min, max;
    for (let i = 0; i < Math.floor(array.length / 2); i++) {
        min = i;
        max = i;

        for (let j = i + 1; j < array.length - i; j++) {
            if (array[min] > array[j]) min = j;
            else if (array[max] < array[j]) max = j;
        }

        if (min !== i) {
            if (max === i) max = min;
            const temp = array[min];
            array[min] = array[i];
            array[i] = temp;    
        }

        if (max !== i) {
            const temp = array[max];
            array[max] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
    }
}

function solution(participant, completion) {
    doubleSelectionSort(participant);
    doubleSelectionSort(completion);

    for (let i = 0; i < completion.length; i++) {
        if(participant[i] !== completion[i]) return participant[i];
    }
    return participant.pop();
}

정확성 테스트

테스트 1 〉	통과 (0.13ms, 29.8MB)
테스트 2 〉	통과 (0.17ms, 30MB)
테스트 3 〉	통과 (31.84ms, 32.8MB)
테스트 4 〉	통과 (37.47ms, 32.6MB)
테스트 5 〉	통과 (37.29ms, 32.9MB)

 

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

 

결과: 이것도 시간초과 ㅠㅠ