버블 정렬

버블 정렬은 현재 배열 요소와 그 다음 배열 요소를 비교한다음 조건에 걸리면 교환하는 식의 정렬이다. 예를들어 배열의 0번 인덱스의 요소와 1번 인덱스의 요소를 비교하고, 그 다음 1번 인덱스의 요소와 2번 인덱스의 요소를 비교하는식이다.

Big O

• Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
• Best Case: O(n): 이미 정렬이 되어있는 경우

버블 정렬은 최악의 경우에 O(n^2)의 시간 복잡도를 가진다. 왜냐하면 각 자리를 찾기 위해서 n번의 순회를 해야하며 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다. 그러나 이미 정렬이 되어있는 경우에는 한 번의 순회로 정렬 여부를 알 수 있다.

장점

버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 여기서 "in place"라는 것은 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.

또한 구현하기 매우 쉽다는 장점도 있다. 그 외에도 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수도 있다.

단점

버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다. 왜냐면 최악의 경우 O(n^2)이 소요되기 때문이다. 만약 데이터가 위 이미지처럼 5개밖에 없다면 최대 25번 순회를 해야하지만 데이터가 1,000개라면 1,000,000번이나 순회를 해야한다.

Stable

버블 정렬은 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable한 정렬이다. 여기서 stable이라는 뜻은 중복 데이터가 있는 경우에 기존 중복 데이터의 순서가 정렬이 다 끝난 이후에도 유지되는 정렬을 말한다.

구현

function bubbleSort (array) {
  for (let i = 0; i < array.length; i++) {//array길이만큼 반복한다.
    let swap;
    for (let j = 0; j < array.length - 1 - i; j++) {
      //i값만큰 이미 정렬 되어있기 때문에 array.length - 1 - i까지만 확인
      if (array[j] > array[j + 1]) {
        swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
    if (!swap) {//swap에 값이 없으면 정렬이 이미완료된 상태
      break;
    }
  }
  return array;
}

출처: Code Playground