버블 정렬(Bubble Sort)

가장 기본적인 정렬 알고리즘으로
거품처럼 배열 내 서로 인접한 두 원소들을 비교하고 교환하여 정렬하는 방식

• 인접한 원소 중 더 큰 숫자를 오른쪽으로 교환하며 정렬(오름차순 기준)

  ⇒ 큰 걸 먼저 찾아 위치해두는 방식
  

• 안정 정렬(Stable Sort)

• 데이터가 거의 정렬된 경우 효율적이지만, 일반적으로 다른 정렬 알고리즘보다 성능이 떨어짐

진행 과정(오름차순 기준)

1. 루프를 돌면서 i 원소와 i+1 원소를 비교
2. i 원소가 더 크다면 i+1 원소와 교환
3. 첫번째 루프를 돌면 제일 큰 값이 배열 맨 오른쪽 값으로 위치
4. 다음 루프를 돌 때마다 정렬할 항목이 1개씩 줄어들며 모든 루프가 종료되면 정렬 완료

구현 코드(오름차순 기준)

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

  for (let i = 0; i < n; i++) {
    let swapped = false; // 교환 여부 확인용 변수

    // 바깥 루프에서 점점 더 큰 숫자들이 뒤로 가므로 비교 범위를 줄임
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 원소를 교환
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 구조 분해 할당을 사용한 교환
        swapped = true;
      }
    }

    // 한 번의 순회에서 교환이 없으면 정렬 완료
    if (!swapped) break;
  }

  return arr;
}

// 테스트
const testArr = [5, 2, 9, 1, 5, 6];
console.log(bubbleSort(testArr)); // [1, 2, 5, 5, 6, 9]

최적화된 코드

const bubbleSort = (arr) => {
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    let swapped = false; // 교환 여부 확인용 변수

    // 바깥 루프에서 점점 더 큰 숫자들이 뒤로 가므로 비교 범위를 줄임
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 원소를 교환
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 구조 분해 할당을 사용한 교환
        swapped = true;
      }
    }

    // 한 번의 순회에서 교환이 없으면 정렬 완료
    if (!swapped) break;
  }

  return arr;
};

const testArr = [5, 2, 9, 1, 5, 6];
console.log(bubbleSort(testArr)); // [1, 2, 5, 5, 6, 9]

시간 복잡도 및 공간복잡도

• 시간복잡도
  • 최선: O(n) (이미 정렬된 경우, 한 번의 반복 후 종료)
  • 평균: O(n²)
  • 최악: O(n²) (완전히 역순으로 정렬된 경우)
• 공간 복잡도
  • O(1) (추가적인 메모리 사용 없음)