정렬_ 버블 정렬(Bubble Sort)

📒 오늘의 공부

정렬_버블 정렬(Bubble Sort)

1. 버블 정렬(Bubble Sort)

• 간단한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하면서 정렬하는 방식
  1. 첫 번째 원소부터 마지막 원소까지 순차적으로 배열을 훑어가면서 인접한 두 원소를 비교
  2. 만약 현재 원소가 다음 원소보다 크면 두 원소를 교환
  3. 이러한 비교와 교환 과정을 배열의 끝까지 진행
  4. 위의 과정을 한 번 수행하면 가장 큰 원소가 배열의 맨 끝으로 이동
  5. 마지막 원소를 제외하고 위의 과정을 반복하고 이를 배열이 정렬될 때까지 반복

2. 버블 정렬 구현

• 버블 정렬 코드

function bubbleSort(arr) {
  const n = arr.length;
  let swapped;

  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
        console.log(arr, arr[i], arr[i + 1]);
      if (arr[i] > arr[i + 1]) {
        // 두 원소를 교환
        const temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);

  return arr;
}

• 예시 문제

const arr = [64, 11, 25, 12,];
bubbleSort(arr);

3. 버블 정렬을 사용하는 이유

• 간단한 알고리즘이기 때문에 개념을 이해하고 구현하기 쉬워 알고리즘의 기본 원리와 동작 방식을 이해하기 위한 교육적인 목적으로 사용
• 실제로는 대규모 데이터에 사용하기엔 비효율적인 알고리즘
  • 버블 정렬의 시간 복잡도는 최악의 경우 O(n^2)로 배열의 크기(n)의 제곱에 비례하는 시간이 소요되기 때문에 대규모 데이터를 정렬할 때는 더 효율적인 알고리즘(ex. 퀵 정렬, 병합 정렬)을 사용하는 것이 좋다.