[25] 삽입 정렬(Insertion Sort)

* 주의! 비전공자가 독학한 내용입니다. 틀린 내용이 있을 수 있으면 댓글로 남겨주세요!

 

1. 2항부터 시작하여 바로 앞의 항과 비교하여 작은 게 앞으로 오게 한다.

2. 다음 항으로 이동하여 1의 과정을 반복한다.

3. 다음 항이 앞으로 왔는데도 그 앞의 항이 더 크면 한 번 더 앞으로 오게 한다.

4. 반복한다.

 

장점: 쉽다. 버블 정렬, 선택 정렬보다 빠르다.

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

 

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전

 

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

 

Insertion Sort로 풀어보기!

function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
        for (let j = i; j > 0; j--){
            if(array[j] < array[j-1]) {
                const temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            } else break;
        }
    }
}

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

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

정확성 테스트

테스트 1 〉	통과 (0.11ms, 29.7MB)
테스트 2 〉	통과 (0.17ms, 30MB)
테스트 3 〉	통과 (31.07ms, 32.2MB)
테스트 4 〉	통과 (9.37ms, 32.7MB)
테스트 5 〉	통과 (34.37ms, 32.6MB)

 

효율성 테스트

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

 

결과: 시간 초과...