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

1. 버블정렬(Bubble Sort)

버블정렬은 인접한 항목의 각 쌍을 비교하여 순서를 정렬하는 알고리즘이다.

 

6 5 3 1 8 7 2 4
> 6, 5 교환
5 6 3 1 8 7 2 4
> 6, 3 교환
5 3 6 1 8 7 2 4
> 6, 1 교환
5 3 1 6 8 7 2 4
> 6, 8 교환x
5 3 1 6 8 7 2 4
> 8, 7 교환
5 3 1 6 7 8 2 4
> 8, 2 교환
5 3 1 6 7 2 8 4
> 8, 4 교환
5 3 1 6 7 2 4 8

 

위처럼 한 번의 반복이 끝나면 가장 큰 숫자가 맨 마지막에 오게 된다.(오름차순 기준)

이를 모든 숫자를 서로 비교할때까지 반복하면 된다.

 

O(n^2)의 시간복잡도를 갖으며, 매우 단순하지만 성능이 좋지 않기 때문에 잘 사용하지 않는다.

 

 

2. 버블정렬 구현

function solution(arr) {
    let answer = arr;
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

자바스크립트로 오름차순 버블정렬 구현하는 방법을 알아보자.

 

for (let i = 0; i < arr.length - 1; i++) { ... }

 

우선 버블정렬의 경우, 한 번의 반복이 끝나면 맨 마지막 숫자는 가장 큰 숫자가 되므로 맨 마지막 숫자를 다른 요소와 비교할 일은 없다.

따라서 for문은 arr.length-1만큼만 반복해 준다.

 

for (let j = 0; j < arr.length - i - 1; j++) {
    if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
}

 

그 후 또 다른 반복문을 이용해 인접한 요소 두 개를 비교해 준다.

반복문의 길이는 정렬된 맨 마지막 숫자는 제외해야 하므로 arr.length - i - 1이 된다.

 

인접한 두 요소를 비교하여, 해당 요소가 더 크다면 두 요소를 바꿔준다.

구조분해할당을 이용해 arr [j] 번째 값은 arr [j+1]로, arr [j+1]은 arr [j]로 맞교환해주면 된다.