버블 정렬 (Bubble sort algorithm)

서론

오늘은 버블 정렬 알고리즘 (bubble sort algorithm)를 알아볼 것이다.

문제 푸는 아이디어

숫자로 이루어진 배열을 오름차순 정렬한다고 해보자.

 

인접한 두개의 요소를 비교한다. i가 i+1 보다 크다면, i와 i+1 을 교체한다. 이를 첫번째 요소부터 n 까지 순회하고 나면, 가장 큰 숫자가 n 번째 자리에 놓일 것이다. 그리고 또 첫번째 요소부터 n까지 순회하면, 두번째로 큰 숫자가 n-1 번째 자리에 놓일 것이다. 이를 n번 반복하면, 모든 배열이 정렬되어 있을 것이다.

[4,3,2,1] 배열을 예시로 들어보자.

1. i=0, i=1 을 비교한다. i=0이 i=1 보다 크기 때문에, 둘을 교체한다. [3,4,2,1]
2. i=1, i=2 을 비교한다. i=1이 i=2 보다 크기 때문에, 둘을 교체한다. [3,2,4,1]
3. i=2, i=3 을 비교한다. i=2이 i=3 보다 크기 때문에, 둘을 교체한다. [3,2,1,4]

이 과정을 거치니, 배열의 요소 중 가장 큰 수인 4가 마지막 index로 갔다.

이를 n 번 반복하면, [1,2,3,4] 가 될 것이다.

시간복잡도

1. 첫번째로 큰 수를 n-1 index로 보내기 : n-1 번 순회
2. 두번째로 큰 수를 n-2 index로 보내기 : n-2 번 순회
3. 세번째로 큰 수를 n-3 index로 보내기 : n-3 번 순회
4. n번째로 큰 수를 1 index로 보내기 : 0번 순회

총합을 구하면, 1+2+…+n-1 = n(n-1)/2 이다.

 

dominant 하지 않은 항을 모두 제거하고 Big O notation 으로 표현하면 O(n^2) 이다. 이것이 Worst 의 경우이고, Best 를 생각해보자.

[1,2,3,4,5] 이미 잘 정렬되어 있는 경우이다.

 

첫번째 순회 (n-1번) 에서 한번도 swap 이 발생하지 않는다면, 이는 이미 정렬되어 있다고 볼 수 있다. 그러므로 Best 에서의 연산횟수는 n-1, 시간복잡도는 O(n) 이다.

공간복잡도

버블 정렬에서 메모리를 얼마나 사용하는지 알아보자. 버블 정렬은 기본 배열의 순서를 swap 하기만 할 뿐, 따로 메모리를 할당하지 않는다. 그러므로 O(1) 이다.

안정성

버블 정렬은 i+1 인덱스가, i 보다 클 때만 순서를 바꿔준다. 그러므로 i와 i+1 이 동일하다면 바꾸지 않고 기존 순서를 유지한다.

즉, 버블 정렬은 안정적인 정렬 알고리즘이다.

예시 코드

function bubbleSort(arr) {
  let temp = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    if (swapped === false) {
      break;
    }
  }
  return arr;
}

마치며

버블 정렬은 O(n^2)의 시간복잡도를 가진다. 다른 정렬은 O(n*logn) 의 시간복잡도를 가질 수 있다. 그러므로, 버블 정렬은 실무에서 유용하게 쓰이지는 않는다. 비교 과정이 직관적이며, 코드도 간단하게 교육적으로 유용한 알고리즘이다.

Reference

Bubble Sort Algorithm - GeeksforGeeks