거품 정렬(Bubble Sort)

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 '서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘' 이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

값을 정렬할 때 발생하는 교환 작업(swap)이 복잡하기 때문에 단순한 알고리즘임에도 불구하고 잘 쓰이지 않는다.

Process

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

JavaScript Code

function bubbleSort(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
      noSwaps = true;
      for (let j = 0; j < i - 1; j++) {
        if (arr[j] > arr[j+1]) {
            let temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            noSwaps = false;        
         }
      }
    if (noSwaps) break;
   }
  return arr;
}

• i라는 변수를 통해 배열의 마지막 지점에서 시작지점까지 순회하는 반복문을 만듭니다
• j라는 변수를 통해 시작점부터 i - 1 까지 순회하는 이중 반복문을 만듭니다
• 배열의 j번째 요소가 j + 1번째 요소보다 크면, 두 개의 위치를 바꿉니다 (Swap)
• 만약 Inner Loop 에서 Swap이 발생하지 않는다면, 모두 정렬된 것이므로 반복문을 종료합니다
• 정렬된 요소를 return 합니다

장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다.
  => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.

단점

• 시간복잡도가 최악, 평균 O(n^2)으로, 굉장히 비효율적이다.
  최선은 O(n)이지만 이미 어느정도 정렬이 되어있는 배열이여야 한다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

 

* 틀린 부분이 있다면 말씀 부탁드립니다!