[알고리즘] 버블 정렬 (Bubble Sort)

버블 정렬은 2중 for문을 사용해

각 순회마다 인접한 요소들을 비교해 조건을 만족할 경우 위치를 스왑하는 방식(한칸씩 미는 방식)으로 요소를 정렬한다.

 

매우 쉽지만, 소팅 방법중에 효율이 나쁜 편에 속한다.

 

작동예시

[3,2,1]을 오름차순 정렬한다고 생각해 보자.

 

첫 번째 반복

arr= [3,2,1]

//i=0. j= 1 to 2 (i+1부터 배열의 길이-1 까지)

[2,3,1] //3과 2를 비교하는데 2가 더 작으므로 위치 스왑 (i=0, j= 1)

[2,1,3] //3과 1을 비교하는데 1이 더 작으므로 위치 스왑 (i=0, j=2)

//첫 번째 반복에서 가장 큰 수는 3으로 결정되었으므로 마지막 요소(arr[2])는 더 이상 검사하지 않음

//i=1. j= 2 to 2 (i+1부터 배열의 길이-1 까지)

[1,2,3] //2와 1을 비교하는데 1이 더 작으므로 위치 스왑 (i=1, j= 1)

//i=2. j= 3 to 2 (조건 불만족; 아무 동작 안함)

 

=> 결과는 [1,2,3]으로 정상적으로 오름차순 정렬됨

 

이렇게 한 칸씩 비교하면서 스왑하는 모습이 마지 거품이 부글거리는 것 같다고 해서 버블정렬이다.

아무튼 그렇다고 한다....

 

Javascript code

const input = [13, 5, 11, 7, 23, 15];

const solution = () => {
    const arr = input;
    for (let l = 0; l < arr.length; l++){
        for (let k = l + 1; k < arr.length; k++){
            if (arr[l] > arr[k]) {
            const temp = arr[l];
            arr[l] = arr[k];
            arr[k] = temp;
            }
        }
    }
    return arr;
};
console.time();
console.log(solution());
console.timeEnd();

 

Time Complexity

각각의 외부 for 순회에 대한 안쪽 for의 순회횟수가 N-K (K는 1부터 N까지; K<=N)이므로,

반복 횟수는 Σ(n=1 to N) N-n 이다.

 

Σ(n=1 to N) N-n

= N^2- Σ(n=1 to N) n

= N^2- N(1+ N)/2

= N^2- (N- N^2)/2

=1/2*N^2- N/2

 

이므로 O( 1/2*N^2- N/2 ) = O(N^2)이다.

 

따라서 버블 정렬의 시간복잡도는 O(N^2)이다.