버블 정렬(Bubble Sort)

📌 버블 정렬

버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 시간 복잡도가 O(n^2)로 연산 수가 가장 많아 정렬 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 편이다.

👀 Example

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

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

bubbleSort([37, 45, 29, 8]);  // [8, 29, 37, 45]

시간 복잡도

• Best: O(n)
• Worst: O(n^2)
• Average: O(n^2)