[ 알고리즘 기법 ] 버블 정렬(bubble sort) 알고리즘 개념 정리

자료구조 \ 알고리즘 기법

[ 알고리즘 기법 ] 버블 정렬(bubble sort) 알고리즘 개념 정리

_moda 2023. 4. 21. 22:40

버블 정렬(bubble sort) 알고리즘 개념 정리

☑️ 버블 정렬 알고리즘이란,

여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘이다.
'거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부른다.

☑️ 버블 정렬 알고리즘의 실행 로직은 아래와 같다.

첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
1~3의 과정을 첫 요소부터 다시 반복합니다.
5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
1~3의 과정을 총 n번(배열의 크기) 반복합니다.

☑️ 버블 정렬 장점

구현이 쉽고 이해하기 쉽다.
정렬 대상의 데이터가 거의 정렬되어 있는 경우에는 매우 빠르게 동작한다.
추가적인 메모리 공간이 필요하지 않다.

☑️ 버블 정렬 단점

평균적으로 나쁜 성능을 보입니다. 정렬 대상 데이터가 역순으로 정렬되어 있는 경우 최악의 성능을 보인다.
요소의 수가 많아질수록 느려진다.
선택 정렬, 삽입 정렬 등과 같은 다른 간단한 정렬 알고리즘에 비해 성능이 떨어진다.

☑️ 버블 정렬 시간 복잡도

버블 정렬의 성능은 입력 데이터의 상태에 크게 영향을 받는다.

정렬되어 있는 경우 : O(n)
- 인접한 두 요소를 비교하며 위치를 바꾸는 과정에서 한 번도 swap이 일어나지 않기 때문이다.
- 바깥쪽 루프는 한 번만 실행되고, 안쪽 루프는 최대 n-1번 실행됨
정렬 안되어 있는 경우 : O(n^2)
- 모든 요소를 한 번씩 비교하며 위치를 바꾸어야 하기 때문이다.
- 바깥쪽 루프는 n-1번 실행되고, 안쪽 루프는 최대 n-1번 실행됨

☑️ 최적화된 버블 정렬 알고리즘

기존의 버블 정렬 알고리즘에서 발생하는 비효율성을 개선한 알고리즘이며,
입력 데이터가 이미 정렬되어 있는 경우를 처리할 수 있도록 개선한 코드이다.
기존의 버블 정렬 알고리즘에서 발생하는 비효율성을 개선한 최적화된 버블 정렬 알고리즘은 입력 데이터가 이미 정렬되어 있는 경우를 처리할 수 있도록 개선되어 있기 때문에 최선의 경우 O(n)의 시간 복잡도를 가지게 된다.
- 그러나, 최악의 경우에는 여전히 O(n^2)의 시간 복잡도를 가지며, 평균적인 경우에는 여전히 O(n^2) 이상의 시간 복잡도를 가지게됨

const swap = function (idx1, idx2, arr) {
  // 두 변수를 바꾸는 방법
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// optimized solution
let bubbleSort = function (arr) {
  let N = arr.length;

  for (let i = 0; i < N; i++) {
    // swap 횟수를 기록한다.
    // 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태이다.
    let swaps = 0;

    // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
    // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
    for (let j = 0; j < N - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swaps++;
        swap(j, j + 1, arr);
      }
    }

    if (swaps === 0) {
      break;
    }
  }

  return arr;
};

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

☑️ 코드 설명

swap 함수는 배열에서 두 인덱스의 요소를 바꿔주는 함수이다.
bubbleSort 함수는 입력으로 배열 arr을 받아서 버블 정렬 알고리즘을 적용한 후, 정렬된 배열을 반환한다.
변수 N은 배열 arr의 길이를 나타낸다.
바깥쪽 for 루프에서는 i번째로 큰 요소가 마지막에서 i번째 위치하게 된다.
이때, 어떤 요소도 swap되지 않은 경우, 배열은 이미 정렬된 상태이므로 루프를 빠져나가게 된다.
안쪽 for 루프에서는 인접한 두 요소를 비교하며 위치를 바꾼다.
이미 정렬된 요소는 고려할 필요가 없으므로, j < N - 1 - i만 비교하면 된다.
만약 요소의 위치가 바뀌면, swaps 변수를 1 증가시키고, swap 함수를 호출하여 요소의 위치를 바꾼다.
안쪽 for 루프를 모두 실행한 후, swaps 변수를 검사하여 어떤 요소도 swap되지 않았으면 더 이상 정렬할 필요가 없으므로 바깥쪽 for 루프를 빠져나간다.
정렬된 배열 arr을 반환한다.

따라서, 이 코드는 기존의 버블 정렬 알고리즘보다 훨씬 효율적이며, 입력 데이터의 상태에 따라서도 빠른 속도로 정렬할 수 있다.