[알고리즘] 버블정렬(Bubble sort)

버블정렬(Bubble sort)

버블정렬은 정렬 알고리즘 종류 중 한 기법으로 길이가 N 인 배열을 정리할때 index 가 0 인 값과 1인 값을 비교한 후 조건에 맞는 값을 왼쪽으로 정렬후 기존 0, 1 인덱스에 각각 1을 더한 값을 반복적으로 비교하여 결과적으로 값의 변화가 아무것도 없을 때 까지 정렬을 반복하는 비교 기반 알고리즘이다.

---

버블정렬, Bubble sort 패러다임 및 동작

버블정렬 패러다임

• 반복(iterative) : 버블정렬은 반복적인 방식으로 배열의 인접한 요소들을 비교하여 정렬한다.
• 비교 기반(comparison based) : 요소 간의 대소 비교를 통해 정렬 순서를 정한다.
• 제자리 (in place) : 추가 메모리 공간을 거의 사용하지 않으며, 기존 배열 내에서만 정렬 작업이 이루어진다.

동작 방식

• 배열을 여러 번 순회하며 인접한 두 요소를 비교하여 크기가 순서에 맞지 않으면 교환(swap) 한다.
• 한 번의 순회 동안 가장 큰 값이 배열의 끝으로 이동하므로, 배열 끝은 정렬된 상태가 된다.
• 배열 전체가 정렬될 때까지 이 과정을 반복한다.

단계별 과정

1. 첫 번째 요소와 두 번째 요소를 비교
2. 두 번째 요소와 세 번째 요소를 비교
3. 이 과정을 끝까지 반복
4. 배열의 끝에 가장 큰 값이 도달한 경우 끝부분은 다시 비교하지 않음
   • 작은 값을 비교하는 경우 배열의 시작에 가장 작은 값이 도달한 경우 처음 부분은 다시 비교하지 않음
5. 배열이 정렬되어 더 이상 요소의 이동이 없을 경우 반복 중단

---

버블정렬 장단점

장점

1. 구현이 매우 간단하다.
2. 데이터가 거의 정렬된 상태일 경우 효율적이다.

단점

1. 데이터 크기가 크면 시간복잡도가 비효율적이다.
2. 보다 효율적인 정렬 알고리즘(Quick Sort, Merge Sort) 와 비교해 성능이 낮다.

---

버블정렬 시간, 공간 복잡도

시간 복잡도

1. 최선의 경우 O(n) : 정렬된 배열인 경우, 교환이 발생하지 않으므로 순회만 수행
2. 최악의 경우 O(n^2) : 역순 배열의 경우, 모든 비교와 교환이 필요
3. 평균  O(n^2)

공간 복잡도

추가적인 메모리 사용이 없어 O(1) 의 공간 복잡도를 갖는다.

---

버블정렬 예제

💡문제
- 함수 bubbleSort()
- 배열 [8, 1, 2, 3, 4, 5, 6, 7] 정렬
- 버블정렬 사용
- 최적화

 

💡구상

버블 정렬을 구현하기 전에 정렬되는 과정을 생각해보자.

 

버블정렬을 사용하면 위와 같은 순서로 배열의 요소가 정렬되고 마지막으로 정렬되고, 마지막으로 한번 더 반복하여 배열의 요소에 변화가 없음을 감지하면 정렬이 종료된다.

 

🔍 코드

function bubbleSort(arr) {
  let j = 0;
  let totalCount = 0;
  while (j !== arr.length - 1) {
    let swap = true;
    for (let i = 1; i < arr.length - j; i++) {
      if (arr[i - 1] >= arr[i]) {
        [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
        swap = false;
      }
      totalCount++;
    }
    if (swap) break; // bubble sort optimization
    j++;
  }
  return arr;
}

 

위의 코드에서 swap 변수로 요소의 변화 여부를 관찰하고 반복문을 도는 동안 한 번이라도 arr[i - 1] >= arr[i] 를 만족하지 않으면 swap 의 상태가 true 로 유지되어 불필요한 반복을 줄여 최적화 할 수 있다.

---

🔥 배운점

버블정렬을 학습하며 기본적인 정렬의 종류중 가장 간단한 형태를 접했는데, 데이터가 큰 경우에서는 좋지 않은 성능을 보여 사실상 학습을 위해 사용하는 경우를 제외하면 실제로 버블정렬을 사용하는 경우가 없지만, 정렬의 과정을 단계적으로 분리하여 반복 과정의 결과를 표시하는 과정을 통해 다른 알고리즘에 접근할 때에도 이런 접근법의 중요성을 다시 한번 생각하게 되었다. 또한, 자바스크립트에서 제공되는 고차함수 sort 함수의 동작원리가 궁금해져 찾아보니 기본적으로 v8 엔진의 sort 함수는 데이터의 길이에 따라 Quick 정렬 또는 Merge 정렬 변형 알고리즘을 사용하는 것을 알게되었다. 좀더 자세히 알기위해 Quick 정렬과 Merge 정렬 학습을 진행해야겠다.