버블 정렬 알고리즘 (Bubble Sort Algorithm)

버블 정렬(Bubble Sort)은 인접한 두 원소를 비교하고 필요에 따라 교환하는 과정을 반복하여 정렬하는 알고리즘입니다. 가장 간단하고 기본적인 정렬 알고리즘 중 하나입니다.

---

예시1)

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

  for (let i = 0; i < n - 1; i++) {
    // 한 번의 반복마다 가장 큰 원소가 맨 뒤로 이동됨
    for (let j = 0; j < n - i - 1; j++) {
      // 인접한 두 원소를 비교하여 필요에 따라 교환
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

// Example usage
const array = [5, 3, 8, 4, 2];
const sortedArray = bubbleSort(array);
console.log(sortedArray); // [2, 3, 4, 5, 8]

위의 코드에서 bubbleSort 함수는 버블 정렬을 수행합니다. 배열의 길이를 나타내는 n 변수를 사용하여 외부 루프를 n-1번 반복하고, 내부 루프를 현재 패스에서 비교해야 할 원소의 개수만큼 반복합니다. 인접한 두 원소를 비교하여 필요에 따라 교환하는 과정을 반복하여 가장 큰 원소가 맨 뒤로 이동합니다. 이렇게 외부 루프와 내부 루프를 반복하면서 배열이 정렬됩니다.

---

예시2)

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

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 원소를 교환
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

// Example usage
const array = [9, 4, 7, 2, 1, 5];
const sortedArray = bubbleSort(array);
console.log(sortedArray); // [1, 2, 4, 5, 7, 9]

위의 코드에서 bubbleSort 함수는 주어진 배열을 버블 정렬 알고리즘을 사용하여 오름차순으로 정렬합니다. 배열의 길이를 나타내는 n 변수를 사용하여 외부 루프를 n-1번 반복하고, 내부 루프를 현재 패스에서 비교해야 할 원소의 개수만큼 반복합니다. 인접한 두 원소를 비교하여 순서가 잘못된 경우에는 교환합니다. 이렇게 외부 루프와 내부 루프를 반복하면서 배열이 정렬됩니다.

 

버블 정렬은 간단하고 이해하기 쉬운 알고리즘이지만, 최악의 경우 시간 복잡도가 O(n^2)이기 때문에 큰 데이터셋에서는 효율적이지 않을 수 있습니다.