Bubble Sort(버블정렬)에 대해서 알아보자! feat.JavaScript

Bubble Sort(버블정렬)

버블 정렬은 요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이라는

이름이 붙여졌다고 합니다. gif를 보시면 요소들이 버블(?)답군요

버블 정렬은 두 인접한 원소를 검사해서 정렬하는 방법입니다. 예를 들어서 1,2 비교 4,5 비교

이런 식으로 더 작은 값을 왼쪽으로 하나씩 옮기는 방식을 사용합니다.

이 방법을 사용하면 한번 사이클을 돌리면 맨 뒤에 값은

무조건 제일 큰 값이기 때문에 검사하지 않아도 됩니다.

매우 쉽게 구현할 수 있지만 일반적으로는 잘 사용하지 않습니다.

그 이유는 O(n²)라는 성능을 가지고 있기 때문입니다.

안정정렬(Stable Sort)

또한 버블 정렬은 안정정렬(Stable Sort)입니다. 안정정렬은 무엇이냐면

정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 되는 알고리즘을 안정정렬이라고 합니다.

[3, 2, 1, 5¹, 7, 5²] 배열이 있습니다.

이를 오름차순으로 정렬한다고 할 때

[1, 2, 3, 5¹, 5², 7]이 된다면 안정 정렬

[1, 2, 3, 5², 5¹, 7]이 될 수 있다면 불안정 정렬입니다.

제자리 알고리즘(in place)

버블 정렬은 제자리 알고리즘으로 자료 구조를 추가로 사용하지 않고 입력을 반환하는 알고리즘입니다.

메모리를 추가로 거의 사용하지 않습니다 (조금 더 사용할 수는 있음)

시간 복잡도

• 최악 O(n²) : 정렬이 하나도 되지 않을 경우
• 최선 O(n) : 이미 정렬이 되어있는 경우

버블 정렬은 최악의 경우에 O(n²)의 시간 복잡도를 가집니다. 왜냐하면 각 자리를 찾기 위해서 n번의 순회를

해야 하며 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야 하기 때문이죠. 그러나 이미 정렬이 되어있는

경우에는 한 번의 순회로 정렬 여부를 알 수 있습니다.

구현 코드

const N = 6;
let data = [3, 5, 6, 7, 2, 1];

for (let i = 0; i < N; i++) {
  let temp;
  for (let j = 0; j < N - 1 - i; j++) {
    if (data[j] > data[j + 1]) {
      temp = data[j];
      data[j] = data[j + 1];
      data[j + 1] = temp;
    }
  }
}
console.log(data);

data라는 배열을 순회하면서 양옆의 숫자를 비교해서 더 작은 값을 왼쪽으로 옮깁니다.

제일 큰 값이 맨 뒤로 가기 때문에 순회할 때마다 -1씩 덜 순회하게 됩니다.