[23] 버블 정렬(Bubble Sort)

* 주의! 독학한 내용으로 틀린 내용이 있을 수 있으며, 댓글로 알려주세요!

 

앞에서 두 개를 비교해 뒤에 있는 것이 작을 경우 바꿔준다.

다음 칸으로 가서 두 개를 비교해 뒤에 있는 것이 작을 경우 바꿔준다.

끝까지 실행한 다음 다시 처음부터 반복한다.

바뀌는 것이 없을 때까지(최악의 경우 배열의 길이 - 1 번) 반복한다.

 

장점: 쉽다!

단점: 느리다!(시간복잡도가 O(n^2)이다.)

 

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전

 

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

 

Bubble Sort로 풀어보기!

function bubbleSort(array) {
    for (let i = 0; i < array.length - 1; i++) {
        let isChanged = false;

        for (let j = 0; j < array.length -1; j++) {    
            if(array[j] > array[j+1]) {
                c = array[j];
                array[j] = array[j+1];
                array[j+1] = c;
                isChanged = true;
            }
        }

        if (!isChanged) break; 
    }        
}

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

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

    return participant.pop();
}

정확성 테스트

테스트 1 〉	통과 (0.14ms, 29.9MB)
테스트 2 〉	통과 (0.14ms, 29.9MB)
테스트 3 〉	통과 (35.54ms, 32.6MB)
테스트 4 〉	통과 (51.07ms, 32.7MB)
테스트 5 〉	통과 (53.68ms, 32.7MB)

 

효율성 테스트

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

 

결과는 시간초과 실패!

 

역시 느리다!