[정렬 알고리즘] 버블정렬 with JS

버블정렬

버블 정렬(Bubble Sort)은 서로 인접한 두 원소를 비교하며 정렬하는 알고리즘입니다. 구현이 간단하나 시간복잡도가 높기 때문에 큰 데이터셋에는 적합하지 않습니다.

---

코드

// 배열의 비교인덱스의 요소를 배열 길이 만큼 반복하여 서로 비교 후 자리를 바꾸는 알고리즘
function bubbleSort(array) {
  const length = array.length;

// 시작인덱스: i -> 배열 길이 만큼 반복을 실행하는 용도이지 비교를 위해 사용하지 않습니다.
  for (let i = 0; i < length; i++) {
    //비교인덱스: j, j+1 -> 실질적으로 배열의 원소를 비교할 때 쓰입니다.
    for (let j = 0; j < length - 1; j++) {
      if (array[j] > array[j + 1]) {
        // 인접한 두 원소를 비교하여 자리를 바꿉니다.
        const temp = array[j]; //temp에 j 인덱스의 값을 임시저장합니다.
        array[j] = array[j + 1];  //기존 j 인덱스의 자리에 j+1 인덱스의 값으로 대체합니다.
        array[j + 1] = temp; // j+1 인덱스의 자리에는 임시로 저장한 temp 즉, j 인덱스의 값을 저장합니다.
      }
    }
  }

  return array;
}

             j j+1
const arr = [3, 2, 1, 5, 4];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5]

---

시간복잡도

버블 정렬의 시간복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)입니다. 이는 배열의 길이가 n일 때,  n-1번의 패스를 수행하면서 각 패스마다 비교 연산을 n-1번 수행하기 때문입니다.

 

다시 말해, 배열의 길이가 n 이라면, 외부 for문이 n 번 반복을 돌 때, 내부 for 문도 반복해서 n-1번 만큼 비교 연산을 중복해서 수행하므로, 거시적인 관점에서 본다면  n*n 이 되어 n^2가 됩니다. 

 

또한, 버블 정렬은 정렬이 진행될수록 정렬이 끝난 부분은 비교할 필요가 없어지므로, 최선의 경우인 이미 정렬된 배열에서는 이점을 가지게 됩니다. 즉, 이미 정렬된 배열에서는 n-1번만 비교하면 되므로 시간복잡도가 O(n)이 됩니다.

---

 공간복잡도

버블 정렬의 공간복잡도는 O(1) ; 상수시간 복잡도 입니다. 이는 배열의 요소를 서로 교환하는 데에만 상수 개의 변수가 필요하기 때문입니다. 따라서 입력 배열 이외에 추가적인 공간을 필요로 하지 않습니다. 즉, 정해진 변수 공간을 제외하고는 추가적인 공간이 없다는 소리입니다.

 

하지만, 버블 정렬은 다른 정렬 알고리즘에 비해 비교적 느리며, 배열이 클수록 성능이 저하됩니다. 따라서 일반적으로 버블 정렬은 작은 크기의 배열이나 정렬이 이미 거의 완료된 배열에서 사용됩니다.