[JavaScript] 버블정렬

버블 정렬 (Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 두 인접한 요소를 비교하여 크기 순서에 맞게 반복적으로 교환하는 방식으로 동작합니다. 정렬이 끝날 때까지 가장 큰 값(또는 작은 값)이 거품처럼 끝으로 이동하기 때문에 버블 정렬이라 부릅니다.

---

동작 원리

1. 배열의 처음부터 시작해서 두 개의 인접한 요소를 비교합니다.
2. 두 요소가 잘못된 순서(예: 오름차순에서 앞 값이 더 크거나, 내림차순에서 더 작음)라면 교환합니다.
3. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 배열의 마지막으로 이동합니다.
4. 이 과정을 배열의 길이만큼 반복하면서 정렬을 완성합니다.

---

장단점

• 장점: 구현이 매우 쉽다.
• 단점: 시간 복잡도가 비효율적이다 (O(n2)O(n^2)O(n2)).
• 적합한 경우: 데이터가 거의 정렬되어 있는 경우.

---

예시 코드 (JavaScript로 구현)

1. 오름차순 버블 정렬

const bubbleSort = (array) => {
  const arr = array.slice(); // 원본 배열을 복사
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) { // 총 n-1번 반복
    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]];
      }
    }
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(bubbleSort(an)); // [1, 2, 4, 5, 8]

 

2. 내림차순 버블 정렬

const bubbleSortDesc = (array) => {
  const arr = array.slice();
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    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]];
      }
    }
  }

  return arr;
};

const an = [5, 1, 4, 2, 8];
console.log(bubbleSortDesc(an)); // [8, 5, 4, 2, 1]

 

버블 정렬 동작 예시

배열: [5, 1, 4, 2, 8] (오름차순 정렬)

1단계 (첫 번째 패스):

• 비교: 5와 1 → 교환 → [1, 5, 4, 2, 8]
• 비교: 5와 4 → 교환 → [1, 4, 5, 2, 8]
• 비교: 5와 2 → 교환 → [1, 4, 2, 5, 8]
• 비교: 5와 8 → 그대로 → [1, 4, 2, 5, 8]

2단계 (두 번째 패스):

• 비교: 1과 4 → 그대로 → [1, 4, 2, 5, 8]
• 비교: 4와 2 → 교환 → [1, 2, 4, 5, 8]
• 비교: 4와 5 → 그대로 → [1, 2, 4, 5, 8]

3단계 (세 번째 패스):

• 비교: 1과 2 → 그대로 → [1, 2, 4, 5, 8]
• 비교: 2와 4 → 그대로 → [1, 2, 4, 5, 8]

결과: [1, 2, 4, 5, 8]

---

시간 복잡도

• 최선의 경우 (이미 정렬된 경우): O(n)O(n)O(n) → (최적화를 추가하면)
• 평균/최악의 경우: O(n2)O(n^2)O(n2)