버블 정렬

거품처럼 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬(거품 정렬)로 불린다.

데이터를 두 개씩 묶어서, 더 큰 값이 뒤로 가도록 자리를 바꿔가며 정렬이 진행된다.
처음부터 끝까지 한 번 정렬을 했다면, 다시 처음부터 끝까지 정렬을 하고,
이 것을 배열의 길이만큼 반복한다.

한 번의 정렬이 끝나면 가장 큰 값을 가졌던 데이터는 맨 뒤로 옮겨지므로,
다음 정렬부터는 이 부분을 제외하고 연산해야한다.

즉, n번째 정렬이 끝나면, 뒤에서 n번째 자리의 데이터가 확정된다.(정렬된다)

두 값 a,b를 정렬할 때는, 임시로 a의 값을 넣어둘 temp가 필요하다.

Big O

하나도 정렬이 안되어 있다면 O(n^2) 의 시간복잡도를 가진다.
각 자리를 찾기 위해서 n번의 순회를 해야하며,
n번의 회전동안 요소의 개수만큼 또 순회를 해야하기 때문이다.

모두 정렬이 되어있는 상태라면 O(n) 의 시간복잡도를 가진다.
이 때는 한 번의 순회로 정렬 여부를 알 수 있다.

장점

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

구현이 쉽다.

이미 정렬된 데이터를 순회하는 경우에는 O(n) 만 순회하면 되기 때문에 정렬 여부를 테스트하는 용도로 사용될 수 있다.

단점

최대 O(n^2) 이 소요될 수 있으므로 자료의 개수가 많아지면 성능이 매우 떨어진다.
데이터가 1000개만 있어도 1000의 제곱만큼 순회해야하기 때문이다.

Stable

버블 정렬은 중복 데이터 값을 처리할 때는, 위치를 교환하지 않기 때문에 stable 한 정렬이다.
stable 은 중복 데이터가 있을 경우, 기존 중복 데이터의 순서가 정렬이 끝나도 유지된다는 것이다.

위 그림이 stable 한 정렬을 보여준다.(손으로 그려서 조잡하다 ㅎ)

구현 방법

function bubbleSort(array) {
  // 배열의 길이만큼 반복한다.
  for (let i = 0; i < array.length; i++) {
    let swap;

    // array[i]와 array[i + 1]을 비교하므로 i보다 1 작은 범위까지 반복해야하고,
    // 정렬이 한 번 끝날 때마다 마지막 데이터의 정렬이 끝나기 때문에
    // i만큼 빼줘야한다.
    for (let j = 0; j < array.length - 1 - i; j++) {
      // 현재 원소값이 다음 원소값보다 크면
      if (array[j] > array[j + 1]) {
        // swap에 현재 값을 넣고
        swap = array[j];

        // 현재 원소값의 인덱스에는 다음 원소값을 넣는다.
        array[j] = array[j + 1];

        // 다음 원소값의 인덱스에는 swap에 넣어둔 현재 원소값을 넣는다.
        array[j + 1] = swap;
      }
    }

    // 위 반복이 끝나면 0번 인덱스의 정렬이 끝난 것이다.
    // 그 것을 한번 회전했다고 표현하겠다.
    // 다음 반복은 다시 0번 인덱스부터 비교를 시작한다.
    console.log(`${i}회전: ${array}`);

    // 만약 두 번째 for문에서 아무런 연산이 진행되지 않으면
    // 더 이상 정렬 할 필요가 없다고 판단한다.
    // 이 때, swap은 undefined 상태로 남아있기 때문에
    // 첫 번째 for문을 break 한다.
    if (!swap) {
      break;
    }
  }

  return array;
}

// [5,4,3,2,1] 배열을 버블 정렬한다.
console.log(bubbleSort([5, 4, 3, 2, 1]));

결과는 아래와 같이 나오게 된다.

참고 자료

본 게시물은 제이JY님의 블로그 글을 인용하여 작성되었습니다.
제이JY님의 tistory 블로그
인프런 Minseok Heo님의 성공적인 코딩 인터뷰를 위한 코딩 인터뷰 정복하기 - 코딩 테스트