정렬 - 버블, 삽입, 선택 정렬 차이점에 대해서 알아보자

정렬 알고리즘 중 버블, 선택, 삽입 정렬에 대해서 정리한 내용을 공유하려고 합니다.
이 세정렬의 공통점은 다음과 같습니다.

• 모두 같은 최악, 최선의 시간복잡도를 갖는다.
• 단순 정렬이다. (구현이 간단하다)
• 작은 데이터의 정렬에 적합하다.
• 제자리 정렬 알고리즘이다. (추가적인 배열이나 리스트를 사용하지 않고, 주어진 배열 내에서 요소를 교환하여 정렬합니다.)

이러한 세 정렬에 대해서 각각 알아보고자 합니다.

버블 정렬

버블 정렬은 이름처럼 인접한 두 요소를 비교하며, 값이 "버블"처럼 배열의 끝으로 올라가는 방식으로 동작합니다.
간단한 정렬 알고리즘 중 하나로, 구현하기는 쉽지만 시간 복잡도가 좋지 않아 실제 환경에서는 거의 사용되지 않는다고 합니다.

버블 정렬의 기본 개념

버블 정렬의 핵심 로직은 다음과 같습니다. (엄청 간단합니다):

1. 배열에서 인접한 두 요소를 비교합니다.
2. 각 반복이 끝날 때마다 가장 큰(혹은 작은) 값이 배열의 끝에 정렬됩니다.
3. 이후에는 정렬이 완료된 마지막 요소를 제외하고 다시 비교를 반복합니다.
4. 이를 배열의 모든 요소가 정렬될 때까지 반복합니다.

버블 정렬의 기본 구현 (JavaScript)

다음은 버블 정렬 알고리즘을 자바스크립트로 구현한 코드입니다.

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

간단히 구현할 수 있지만, 이 방식에는 비효율적인 점이 있습니다.

위 코드의 최악 및 평균 시간 복잡도는 O(n²)입니다. 이유는 모든 요소를 반복적으로 비교해야 하기 때문입니다. 다만, 개선할 여지가 있는데요. 만약 배열이 이미 정렬된 상태라면 불필요한 연산을 줄일 수 있습니다.

정렬이 이미 끝난 상태라면 반복문을 더 이상 실행할 필요가 없습니다. 이를 위해 flag(플래그)를 사용하여 최적화할 수 있습니다. 수정한 버블 정렬 코드는 다음과 같습니다:

function bubbleSort(list) {
  let isChanged = false;

  for (let i = list.length - 1; i >= 0; i--) {
    console.log("hi");
    for (let j = 0; j < i - 1; j++) {
      let swap = list[j];
      let next = list[j + 1];

      if (swap > next) {
        list[j] = next;
        list[j + 1] = swap;
        isChanged = true;
      }
    }
    if (!isChanged) {
      break;
    }
    isChanged = false;
  }
  return list

시간 복잡도

개선된 시간 복잡도는 다음과 같습니다.

최악의 경우 (배열이 완전히 정렬되지 않은 경우) : 𝑂(𝑛2)
최선의 경우 (배열이 이미 정렬된 경우) : 𝑂(𝑛)
평균의 경우 (배열이 랜덤하게 주어진 경우) : 𝑂(𝑛2)

결론적으로, 버블정렬의 경우 요소의 개수가 많아질수록 연산량이 급격히 증가하기 때문에, 실무에서 다루는 대규모 데이터에는 적합하지 않습니다.

삽입정렬

삽입 정렬은 요소를 올바른 위치에 삽입하여 정렬하는 자료구조입니다. 쉬운 예로 손에 든 카드를 정렬하는 방법이 있습니다. 첫번째 카드는 건너뛰고 두번째 카드부터 앞 카드와 비교하면서 정렬해 가는 방법입니다.

삽입 정렬의 기본 개념

삽입 정렬의 로직은 다음과 같습니다.
1. 배열의 두 번째 요소부터 시작합니다. (첫 번째 요소는 이미 정렬된 상태로 간주)
2. 현재 요소가 n번째 라고 한다면, 0부터 n-1까지 돌아가며 현재요소가 삽입할 적절한 위치를 찾습니다.
3. 모든 배열을 순회할때까지 반복합니다.

삽입 정렬의 기본 구현 (JavaScript)

아래는 위 로직을 코드로 구현한것입니다.

function insertionSort(list) {
  for (let i = 1; i < list.length; i++) {
    const current = list[i];
    let compareIndex = i - 1;

    while (compareIndex >= 0 && list[compareIndex] > current) {
      list[compareIndex + 1] = list[compareIndex];
      compareIndex--;
    }

    list[compareIndex + 1] = current;
  }

  return list;
}

삽입정렬또한, 버블정렬과 같은 시간복잡도를 갖습니다.

최악의 경우 (배열이 완전히 정렬되지 않은 경우) : 𝑂(𝑛2)
최선의 경우 (배열이 이미 정렬된 경우) : 𝑂(𝑛)
평균의 경우 (배열이 랜덤하게 주어진 경우) : 𝑂(𝑛2)

정렬시, 요소를 하나씩 뒤로 밀어야 하기때문에 큰 데이터에는 맞지 않은 정렬 방법입니다.

선택 정렬

선택 정렬은 정렬되지 않은 요소들중 가장 작은 값 선택해서 정렬하는 방법입니다. 앞서 설명했던 버블 정렬과 삽입정렬처럼 간단하게 구현할 수 있습니다.

function selectionSort(list) {
  for (let i = 0; i < list.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < list.length; j++) {
      if (list[j] < list[minIndex]) {
        minIndex = j; 
      }
    }

    if (minIndex !== i) {
      const temp = list[i];
      list[i] = list[minIndex];
      list[minIndex] = temp;
    }
  }

  return list;
}

최악의 경우 (배열이 완전히 정렬되지 않은 경우) : 𝑂(𝑛2)
최선의 경우 (배열이 이미 정렬된 경우) : 𝑂(𝑛2)
평균의 경우 (배열이 랜덤하게 주어진 경우) : 𝑂(𝑛2)

선택정렬은 버블 정렬보다 더 나은 복잡도를 갖습니다. 버블 정렬은 불필요하게 많은 스왑 연산을 수행할 수 있고 스왑 연산은 메모리 이동이 발생하기 때문에 비교 연산보다 상대적으로 느릴 수 있습니다. 반면, 선택 정렬은 최소한의 스왑만 수행하기 때문에 메모리 이동이 적어 더 효율적입니다.

시간복잡도는 비교 횟수를 기반으로 계산합니다. 버블 정렬과 선택 정렬 모두 O(n2)번의 비교를 수행하므로, 이론적인 시간복잡도는 동일하게 𝑂(𝑛2) 입니다.

하지만 실제 성능에서는 스왑 횟수가 적은 선택 정렬이 버블 정렬보다 더 빠르게 동작합니다. 이러한 이유는 선택 정렬이 불필요한 메모리 이동을 줄이기 때문입니다.

세 가지 기본적인 정렬 알고리즘(버블 정렬, 삽입 정렬, 선택 정렬)의 성능을 세 가지 다른 상황에서 테스트했습니다.

• 랜덤하게 섞인 배열 : [4, 6, 2, 1, 0, 5, 3, 6, 5]
• 이미 정렬된 배열 : [1, 2, 3, 4, 5, 6, 7, 8, 9]
• 완전히 역순으로 정렬된 배열 : [9, 8, 7, 6, 5, 4, 3, 2, 1]

각 케이스별로 3회씩 실행하여 실행 시간을 측정했습니다.

1. 랜덤 배열의 경우

1회차: 버블(0.374ms) / 삽입(0.196ms) / 선택(0.5ms)
2회차: 버블(0.59ms) / 삽입(0.282ms) / 선택(0.309ms)
3회차: 버블(0.943ms) / 삽입(0.528ms) / 선택(0.599ms)

삽입 정렬이 일관되게 가장 좋은 성능을 보여주었습니다.

2. 정렬된 배열의 경우

1회차: 버블(0.365ms) / 삽입(0.39ms) / 선택(0.36ms)
2회차: 버블(0.42ms) / 삽입(0.413ms) / 선택(0.42ms)
3회차: 버블(0.256ms) / 삽입(0.188ms) / 선택(0.172ms)

세 알고리즘 모두 매우 비슷한 성능을 보여주었습니다.

3. 역순으로 정렬된 배열의 경우

1회차: 버블(0.205ms) / 삽입(0.171ms) / 선택(0.173ms)
2회차: 버블(0.42ms) / 삽입(0.413ms) / 선택(0.381ms)
3회차: 버블(0.19ms) / 삽입(0.188ms) / 선택(0.181ms)

역순 배열을 실행할때, 조금 의외였던 점이 이론적으로는 최악의 케이스여야 하지만, 실제로는 좋은 성능을 보여주었습니다.
세 알고리즘 모두 비슷한 성능을 보여주었고, 어떤 때에는 랜덤한 배열보다 수행시간이 짧았습니다.

결론

정렬 알고리즘의 실제 성능이 이론적 예측과 다를 수 있다는 것을 알게되었습니다. 특히 삽입 정렬이 버블정렬과 선택정렬보다 랜덤 데이터에서 더 나은 성능을 갖는다는걸 알게되었습니다. 물론 데이터가 그렇게 많지 않았고, 제 컴퓨터에서만 돌려본 거라 실제로 엄청 큰 데이터를 다뤄야 하는 상황이라면 결과가 많이 달라질 수 있을것같습니다. 다만, 이 세 정렬을 공부하면서 느끼게 된 것은, '이게 제일 좋은 방법이야!'라고 생각는게 아닌 실제로 어떤 데이터를 다루는지, 어떤 환경에서 돌리는지에 따라서 더 잘 맞는 다른 방법이 있을 수 있기 때문에 상황에 맞는 알맞은 해결 방법을 찾는 문제 해결 능력을 길러야 한다는 생각이 많이 들었습니다.