[JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Selection Sort in JavaScript)

Sorting Algorithm

무작위로 섞여있는 데이터를 어떤 기준에 맞춰 정렬하는 알고리즘은 여러 가지가 있다. 정렬 알고리즘은 다양한 경우에 매우 유용하게 사용된다.

 

1. 각종 데이터 목록을 정리하고 싶을 때
2. 분포도의 중위값을 알아내고 싶을 때
3. 데이터에서 중복값을 잡아내고 싶을 때
4. 이진 탐색을 하고 싶을 때

 

사실 내가 공부하는 자바스크립트에 sort()라는 메소드가 이미 존재하듯이, 모든 프로그래밍 언어에는 자체적인 정렬 메소드가 있다. 그럼에도 불구하고 우리가 정렬 알고리즘을 배워야하는 이유는 시스템 정렬이 항상 좋은 퍼포먼스를 보장하지 않기 때문이다. 또한 내가 가진 데이터베이스의 양이나 상황에 따라 어떤 정렬을 사용하는 것이 좋을지 달라지기 때문에 우리는 기본적으로 유명한 정렬 알고리즘들은 반드시 알고 있어야 한다.

 

오늘은 그 중에서도 가장 기본적이고 쉬운 버블 정렬과 삽입 정렬, 선택 정렬에 대해서 정리해보려고 한다.

 

---

 

Bubble Sort

버블 정렬은 요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이란 이름이 붙여졌다. 버블 정렬은 말로 설명하는 것보다 눈으로 보는 것이 이해하기 쉽기 때문에 아래 gif 이미지를 첨부하였다. 이번주 과제로 만든건데, 버블 정렬을 구현한 후 화면에 애니메이션으로 보여주는 과제였다.

 

Bubble Sort

 

위 그림을 보면 알 수 있듯이 데이터를 두개씩 묶어서 비교한 후 크기가 큰 쪽이 오른쪽으로 가도록 자리를 바꿔가며 크기가 큰 데이터를 오른쪽으로 민다. 그러면 1회전이 끝남과 동시에 이 리스트에서 가장 큰 값이 가장 오른쪽에 가기 때문에 맨 오른쪽 자리가 결정난다. 즉, n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다.

 

 

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이라는 뜻은 중복 데이터가 있는 경우에 기존 중복 데이터의 순서가 정렬이 다 끝난 이후에도 유지되는 정렬을 말한다.

 

Stable sort / Unstable Sort

 

 

function bubbleSort (array) {
  for (let i = 0; i < array.length; i++) {
    let swap;
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
    console.log(`${i}회전: ${array}`);
    if (!swap) {
      break;
    }
  }
  return array;
}
console.log(bubbleSort([5, 4, 3, 2, 1]));

 

자바스크립트로 간단하게 구현해본 버블 정렬이다.

버블 정렬은 다른 고급 정렬들에 비해 구현하기가 매우 쉽다.

 

for문으로 i가 0부터 array.length보다 작을 때까지 loop을 돌리고,

그 안에 j가 0부터 array.length - 1 - i보다 작을 때까지 loop을 돌린다.

array.length - 1 - i인 이유는 일단 array[j]와 array[j + 1]을 비교할 예정이기 때문에

배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 1을 빼줘야하고

두번째로 각 회전이 끝날 때마다 마지막 데이터의 정렬이 끝나기 때문에 i를 빼줘야한다.

 

이제 swap이란 변수를 만들어 array[j]와 array[j + 1]을 비교하여 array[j]가 더 크면 자리를 교환한다.

만약에 각 회전을 끝내고 swap 변수가 undefined상태라면 정렬이 다 되어있다는 뜻이므로 바로 for문을 종료시킨다.

 

 

실행결과

 

---

 

Insertion Sort

삽입 정렬은 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법이다. 

Insertion Sort

 

삽입 정렬은 위 그림처럼 항상 두 번째 요소를 왼쪽 요소와 비교하면서 시작한다. 1회전에서는 왼쪽 요소보다 두번째 요소가 크기 때문에 아무런 일이 일어나지 않는다. 2회전에서는 2를 왼쪽 두 개의 데이터와 비교하여 가장 왼쪽에 끼워넣는다. 3회전에서는 5를 왼쪽 데이터와 비교하여 3과 7 사이에 끼워넣는다. 이런식으로 회전을 하다보면 정렬이 되는 방식이다. 

삽입 정렬은 항상 왼쪽 비교 대상 데이터들이 정렬되어있다는 가정하에 진행된다.

 

 

Big O

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

삽입 정렬 역시 버블 정렬과 똑같은 시간 복잡도를 가진다.

 

 

장점

삽입 정렬도 버블 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다.

 

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

 

 

단점

삽입 정렬 역시 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다.

 

 

Stable

삽입 정렬도 중복된 데이터는 위치를 교환하지 않기 때문에 stable한 정렬이다.

 

 

function insertionSort (array) {
  for (let i = 1; i < array.length; i++) {
    let cur = array[i];
    let left = i - 1;

    while (left >= 0 && array[left] > cur) {
      array[left + 1] = array[left];
      array[left] = cur;
      cur = array[left];
      left--;
    }
  }
  return array;
}

 

처음에 구현한 삽입 정렬 코드이다.

두 번째 요소부터 선택해서 앞의 요소들이랑 비교해야하니까 for문을 1부터 시작한다.

그리고 cur변수에 현재 데이터를 저장하고 left 변수에 i - 1을 넣어준다.

while문을 돌려서 left가 0보다 크거나 같고, array[left]가 cur보다 큰 경우 

두 데이터를 교환하고 cur 변수에 array[left]를 담고 left는 -1을 해준다.

 

즉, 1번째 데이터를 뽑아서 바로 앞의 0번째 데이터와 비교한 후, 0번째 데이터가 더 크면 두 값을 교환한다.

그 다음 2번째 데이터를 뽑아서 1번째 데이터와 비교한다. 1번째 데이터가 더 크면 두 값을 다시 교환하고 

이번엔 1번째 데이터와 0번째 데이터를 비교한다. 0번째 데이터가 1번째 데이터보다 크면 다시 두 값을 교환한다.

만약에 데이터가 원래 정렬되어있었다면 while문 안의 코드는 실행하지 않으므로 O(n) 시간복잡도가 성립된다.

 

이런 식으로 흘러가는데 인터넷을 찾아보니 데이터 교환을 좀 더 간단하게 표현할 수 있다는 사실을 깨달았다.

 

 

function insertionSort (array) {
  for (let i = 1; i < array.length; i++) {
    let cur = array[i];
    let left = i - 1;

    while (left >= 0 && array[left] > cur) {
      array[left + 1] = array[left];
      left--;
    }
    array[left + 1] = cur;
    console.log(`${i}회전: ${array}`);
  }
  return array;
}
console.log(insertionSort([5, 4, 3, 2, 1]));

 

바로 이렇게하면 된다. array[left + 1]에 array[left]값을 넣고 left값을 하나씩 줄여가며 왼쪽과 비교하다가

교환이 다 끝나고 while문을 빠져나오면 맨 앞의 요소에 cur값을 넣는다.

 

 

실행결과

 

---

 

Selection Sort

선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다.

 

1. 먼저 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교환한다.
3. 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다.
4. 그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복

 

버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로

선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다.

다음의 그림을 보면 이해가 쉽다.

 

Selection Sort

 

Big O

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

선택 정렬은 위의 두 정렬과는 다르게 정렬이 이미 되어있는 경우에도 O(n^2)의 시간 복잡도를 가진다.

그 이유는 매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문이다. 그렇기 때문에 성능이 매우 떨어진다.

 

 

장점

선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다.

 

 

단점

선택 정렬은 최선의 경우에도, 최악의 경우에도 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어진다.

 

 

UnStable

선택 정렬은 데이터가 중복된 경우 위치가 바뀔 수 있기 때문에 Unstable한 정렬이다. 

위의 그림을 살펴보면 첫 번째 회전 시에 5가 있는 0번째 칸에 위 리스트의 최소값인 1이 들어가야하므로

1과 5를 교환해야하고 그러면 중복 데이터인 5의 순서가 변하는 것을 알 수 있다.

 

 

function selectionSort (array) {
  for (let i = 0; i < array.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      let swap = array[minIndex];
      array[minIndex] = array[i];
      array[i] = swap;
    }
    console.log(`${i}회전: ${array}`);
  }
  return array;
}
console.log(selectionSort([5, 4, 3, 2, 1]));

 

선택 정렬을 자바스크립트로 구현해보았다.

항상 첫번째 자리를 기준으로 정렬하므로 i는 0부터 시작하고

첫번째 자리를 가장 작은 값이라고 가정하므로 minIndex 변수에 i를 담아준다.

i + 1번째 자리부터 순회하며 array[i]보다 작은 값이 있는지 검사한다.

검사가 끝나고 minIndex값이 i와 같지 않다면 그 값과 i번째 값을 교환한다.

 

 

실행결과

 

1회전만에 정렬이 되었으나 선택 정렬은 데이터가 정렬된 상태에서도 계속해서 순회하며

최소값을 찾는 과정을 하기 때문에 매우 비효율적인 정렬인 것을 확인할 수 있다.