thisyujeong.dev

JavaScript 알고리즘 & 자료구조 마스터 클래스 강의를 듣고 작성하는 강의노트

버블 정렬 (Bubble Sort)

버블 정렬은 효율적이지는 않아 흔히 사용되지는 않는다.

버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

버블 정렬의 작동 방식은 루프를 돌면서 각 항목을 다음 항목과 비교하는 것이다. 어떠한 기준에 부합하다면 두 항목을 교환하고, 다음 항목을 비교하고 부합하다면 비교하고 교환하고.. 를 반복한다. 그리고 이 과정을 첫 항목부터 또 반복한하면 최종적으로 정렬된 배열이 된다.

정렬 과정

예시로 [37, 45, 29, 8] 데이터를 정렬하는 과정

• 1회전
  • [37, 45, 29, 8] ➡ [37, 45, 29, 8] ➡ [37, 29, 45, 8] ➡ [37, 29, 8, 45]
  • 1회전 결과: [37, 29, 8, 45]
• 2회전
  • [37, 29, 8, 45] ➡ [29, 37, 8, 45] ➡ [29, 8, 37, 45]
  • 2회전 결과: [29, 8, 37, 45]
• 3회전
  • [29, 8, 37, 45] ➡ [8, 29, 37, 45]
  • 2회전 결과: [8, 29, 37, 45]

한 회전(loop)씩 수행할 때마다 가장 큰 자료가 맨 뒤로 이동한다. 즉, 1회전 때는 맨 끝의 자료가 확정되므로 더 이상 비교할 필요가 없고, 2회전 때는 끝에서 두번째 자료가 확정되므로 이 또한 비교할 필요가 없다. 이렇게 한 회전 수행할 때마다 정렬에서 제외되는 데이터가 하나 씩 늘어난다.

의사코드

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        //SWAP!
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
 
bubbleSort([37, 45, 29, 8]);

버블 정렬 최적화

예시로 [8, 1, 2, 3, 4, 5, 6, 7] 데이터를 정렬하려고 할 때 1회전을 하면 더이상 정렬할 필요가 없어진다. 이때 이전 루프에서 교환이 이루어지지 않았다면 정렬이 완료된 상태로 간주하여 더이상 검색을 정렬을 시도하지 않도록 리팩토링 할 수 있다.

function bubbleSort(arr) {
  let swaps;
  for (let i = arr.length; i > 0; i--) {
    swaps = false;
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) {
        //SWAP!
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swaps = true;
      }
    }
    if (!swaps) break;
  }
  return arr;
}
 
bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]);

swaps라는 변수를 생성하여 true 라면 교환이 이루어졌음을, false 라면 교환이 이루어지지 않았음을 판단해 false가 되면 break 문을 통해 중단시킨다. 이 과정은 2회전만으로 정렬이 완료되어 정렬 시간을 단축 시켰다.

시간 복잡도

• Best: O(n)
• Worst: O(n²)
• Average: O(n²)