JavaScript로 알아보는 버블 정렬(Bubble Sort)과 예제 코드

https://www.resultswebdev.com/bubble-sort-algorithm/

소개

버블 정렬(Bubble Sort)은 가장 간단하고 기본적인 알고리즘 중 하나로, 이름에서도 알 수 있듯이 배열의 요소를 '거품(Bubble)'처럼 서로 교환해 가며 정렬하는 방식입니다.

즉, 서로 인접한 두 원소를 비교해가며 오름차순이나 내림차순으로 정을 진행합니다.

기본 개념

버블 정렬의 개념은 만약 숫자 배열을 오름차순으로 정렬하는 상황에서 더 큰 숫자가 한 번에 하나씩 뒤로 이동하는 방법입니다.

기본적으로 어떤 항목이 더 크면 교환하고, 다음 항목과 비교하고, 다음 항목보다 더 크면 또 교환을 하고, 다시 다음 항목과 비교하면서 반복을 합니다.

오름차순의 상황에서는 가장 큰 값이 상단을 향해서 값을 정렬하는 방식으로 목록을 만듭니다.

예제 코드 #1

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

기본적인 버블 정렬 코드입니다.

해당 코드는 이중 반복문을 통해서 인접한 원소에 대해서 크기를 비교하며 위치를 바꾸면서 정렬을 진행합니다.

 

하지만 이 코드는 이미 정렬이 된 상태에서는 버블 정렬이 작동하는 원리 때문에 끝 부분에 index가 없는 곳과 비교해서 undifined와 무의미한 비교를 하고, 이미 정렬이 된 상태에서도 불필요한 연산을 하 반복문을 돌게 됩니다.

 

즉, j < arr.length 조건 때문에 arr[j + 1]가 배열 범위를 초과하는 경우가 생깁니다.

그래서 마지막 요소와 undefined를 비교하는 문제가 발생합니다.

이렇게 되면 불필요한 연산을 수행하게 됩니다.

최적화된 코드

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

j < arr.length - i - 1로 마지막 요소와 undefined를 비교하는 문제를 해결할 수 있습니다.

그리고 첫번째 예제 코드에서는 이미 정렬이 된 상태에서도 반복문이 돌면서 연산을 수행하지만 해당 코드는 반복문이 진행되면서 교환 작업이 없다면 배열은 이미 정렬된 것으로 간주하고 프로그램을 종료하게 됩니다.

 

따라서, 배열이 거의 정렬된 상태라면 배열의 길이가 길어짐에 따라 전 코드와는 아주 큰 차이가 생깁니다.

버블 정렬의 시간 복잡도(Big O)

배열의 각 항목마다 n번의 비교를 하고 배열의 다른 모든 항목 하나하나 비교하기 때문에 일반적으로 버블 정렬의 시간 복잡도는 O(N^2)입니다.

 

그러나 데이터가 거의 정렬되었거나 이미 정렬이 완료된 상태에서 noSwaps 변수가 있는 코드를 사용하면 선형 시간(Linear Time)에 가까워집니다. 예를 들어, [1, 2, 3, 4, 5]와 같은 이미 오름차순으로 정렬된 배열에서는 첫 번째 패스 동안 어떠한 교환도 발생하지 않아 알고리즘이 즉시 종료됩니다.

따라서 이 경우 버블정렬의 시간 복잡도는 O(N)으로 줄어들게 됩니다.

다만 주목해야 할 점은 이러한 최적화 사항들은 '최선'의 경우에 해당하며 일반적인 상황에서 버블정렬은 여전히 O(N^2)의 시간 복잡도를 가진다는 것입니다.