빅 오 표기법 2. 버블 정렬

정렬 알고리즘 중 기본인 버블 정렬의 사용법

 

1. 배열 내에서 연속된 두 항목을 가르킨다.

2

1

3

5

2. 두 항목의 순서가 바뀌었으면(왼쪽값이 오른쪽값보다 크면) 항목을 바꾼다

1

2

3

5

3. 포인터를 한칸 이동하여 반복한다.

1

2

3

5

 

1 ~3 을 반복하는 것을 패스스루 라고 한다.

패스스루가 끝나면 마지막 원소 즉, 5를 빼고 다시 패스스루를 반복한다.

(총 행의 수 - 1 ) 의 패스스루를 반복한다. 위의 예시에선 3번의 패스스루가 일어난다.

위에 예시에선 결국 (N-1) + (N-2)...+ 1번의 비교를 수행한다. 위의 예시에선 3+2+1=6번의 비교가 일어난다.

여기에 더해 만약 모든 수가 역순일경우엔 총 6번의 교환이 더 일어나게 된다. 총 12단계의 작업이 일어난다.

 

원소 N개	최대 단계 수	버블 정렬의 단계 수	N^2(버블 정렬의 비효율성)
4	12	12	16
5	20	20	25
10	90	90	100
20	380	380	400
40	1560	1560	1600
80	6320	6320	6400

※ N^2를 이차 시간 이라고도 부른다.

 

function hasDuplicateValue(array) {
	var steps = 0;
	for(var i = 0 ; i < array.length ; i++ ){
    	for(var j = 0 ; j < array.length ; j++ ){
        	steps++;
        	if(i !== j && array[i] == array[j]) {
            	return true;
            }
        }
    }
    console.log(steps);
    return false;
}

배열 중복 값이 있는지 확인하는 자바스크립트다. 위의 코드가 잘 동작하겠지만 너무나도 비효율적인다.

hasDuplicateValue([1, 2, 3])으로 실행하면 콘솔엔 9가 찍힌다.

 

 

function hasDuplicateValue(array) {
	var steps = 0;
	var existingNumbers = [];
    for(var i = 0 ; i < array.length ; i++ ){
    	steps++;
    	if(existingNumbers[array[i]] === undefined) {
        	existingNumbers[array[i]] = 1;
        } else {
        	return true;
        }
    }
    console.log(steps);
    return false;
}

다음은 코드단계 수를 좀더 최적화 한 것이다.

existingNumbers엔 배열을 기록해둔것이다.

[3, 5, 8]을 넣어 돌리면 [undefined, undefined, undefined, 1, undefined, 1, undefined, undefined, 1]가 나온다.

즉 array엔 3, 5, 8이 있다는 뜻이 된다. 콘솔엔 3이 찍히며 결국 O(N)이라는 결론이 나온다.

위의 코드 O(N^2)보다 아래 코드 O(N)가 훨씬 빠르고 효율적이다.