Bubble Sort

버블 정렬은 가장 기본적인 정렬 알고리즘 이다. 다음은 C코드로 작성된 버블 정렬의 예제이다. 버블 정렬은 기본적으로 두 단계로 이루어 져있는데, 비교 와 교환 이다.

void bubbleSort(int[] array, int size) {
	for(int i; i < size; i++) {
    	for(int j; j < size - i; j++) {
        	if(array[j] > array[j+1]) {
            	int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
		}
    }	
}

버블 정렬의 순서는 다음과 같다.

5	1	4	2	3
다음과 같은 배열을 버블정렬을 한다고 가정하자

[5]	1	4	2	3
첫번째 원소부터 시작하여 자기 자신 바로 앞 원소와 크기를 비교한다.
5 > 1 이므로, 5가 더 크므로, 1과 5의 위치를 바꾼다.

1	[5]	4	2	3
5와 4를 비교한다. 5가 더 크므로 바꾼다.

1	4	[5]	2	3

5와 2를 비교한다. 5가 더 크므로 바꾼다.

1	4	2	[5]	3
5와 3을 비교한다. 5가 더 크므로 바꾼다.

1	4	2	3	[5]
더 이상 앞에 숫자가 없으므로, 5는 가장 큰 수이고,  다시 처음으로 돌아가 비교를 시작한다.

[1]	4	2	3	5
위의 과정을 반복한다.

최악의 상황을 고려해보자, 가장 최악의 상황은 1번의 비교마다 1번의 교환이 일어나는 것이다. 즉, 크기가 5인 배열에서 최악의 상황은 첫번째 루프부터 시작해 4 + 3 + 2 + 1 = 10 번의 비교가 일어나고, 각각의 비교에서 모두 교환이 일어나면 최악이므로, 10번의 교환, 총 20단계를 거치게 된다.

N개의 원소를 가진 배열은 (N-1 + N -2 + N-3 .... + 1) * 2 라는 단계를 거치게 된다. 즉, 거의 N^2 만큼의 단계를 거친다. 이를 빅 오 표기법으로 표현하면

O(N^2)

이를 이차시간(Quadratic Time) 이라고 부른다.

이차시간(Quadratic Time) 을 선형시간으로 변환

위의 버블 정렬 알고리즘은 이차시간 알고리즘이다. 원소의 갯수가 늘어날 수 록 시간 복잡도가 기하급수적으로 상승한다. 이는 엄청나게 비효율적인 것이다. 이를 선형시간으로 바꿔 효율적으로 사용할 수는 없을까?

먼저, 단계 상승의 원인을 생각해보자, 이전 글에서 선형시간을 설명할 때, 각각의 배열의 인덱스를 순환하며 출력하는 알고리즘은 N단계를 거친다고 했다. 이 때 사용하던 문법은 for을 활용했다. 버블 정렬은 이중 for 문을 사용한다.

그렇다, 이중 for문이 원인이 되게된다. 이중 for문을 단 하나의 for문으로 변환하여 버블 정렬을 구현하면 선형시간을 가지는 알고리즘으로 변환이 가능하다. 하지만 버블 정렬을 선형 시간 알고리즘으로 바꾸는 것은 불가능 하다. 그리고 버블 정렬 외에 효율적인 정렬 알고리즘들이 존재하므로, 우선은 이차시간을 선형시간으로 변화하는 예제 코드를 살펴보자.

### hasDuplicateValue_before.js

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

위 코드는 인자로 받는 배열에 중복 값이 있는지 확인하고 중복 값이 있다면 true를 반환하고 없다면 false를 반환하는 자바스크립트 알고리즘 코드이다. 위 알고리즘은 당연하게도 이차시간 알고리즘이다. 이를 선형시간으로 바꾼 코드가 바로 아래에 있다.

### hasDuplicateValue_after.js

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

변환된 코드는 먼저 빈 배열을 하나 생성하고, for문을 시작한다. 보면 알겠지만, 빈 배열의 인덱스는 인자로 받은 배열의 값의 매핑이다.

인자로 받은 배열의 값을 하나하나 조회하는데, 만약 배열의 값과 같은 값이 한번도 이전에 나오지 않았다면, 매핑된 배열의 값에 1을 할당하고, 만약 이미 1이라면 true를 반환해 중복되어있음을 알린다. 만약 모두 중복이 아니라면 모든 매핑 배열의 값이 undefined 일것이므로, false를 반환한다.

위의 예제가 이차시간 문제를 선형시간으로 변환하는 좋은 예라고 할 수있다. 여기서 하나의 테크닉을 얻고 가는것이 중요하다. 바로 배열의 값을 통한 인덱스 매핑 테크닉이다. 앞으로 많은 예제에 등장 할 것이다.