200124(금) : Bubble Sort, Insertion Sort

이번 주에는 대표적인 정렬 알고리즘에 대해서 배우는 한 주였다. 총 4개의 정렬 알고리즘 - Bubble, Insertion, Merge, Quick -을 두 편의 글로 나누어서 1) 특징(시간/공간 복잡도, 장/단점 등), 2) 정렬 알고리즘 로직, 3) 구현 방법을 중심으로 정리하고자 한다. 본 글에서는 우선 Bubble Sort와 Insertion Sort를 정리한다.

 

정렬 알고리즘과 관련된 첫 글인만큼, 본격적으로 Bubble Sort를 알아보기 전에 도대체 왜 정렬 알고리즘을 배워야하는지에 대해서부터 살펴보자. 다들 아시다시피 자바스크립트에는 이미 내장된 Array.prototype.sort() 메소드가 존재한다. (Sort MDN 문서)

 

이를 사용하면 복잡한 정렬 로직을 알지 못해도 충분히 쉽게 정렬할 수 있는데 왜 대체 정렬 알고리즘을 배워야할까?

 

기업에서는 축적된 데이터를 정렬할 일이 무수히 많이 필요한데 정렬이 필요한 원본 데이터의 type이나 양은 천차만별이다. 모든 데이터가 다 배열로만 이루어져있고, 또 데이터의 크기도 끽해봐야 100개 1000개 남짓이면 상관없겠지만 기업에서는 상상할 수 없는 크기의 수 많은 데이터를 정렬해야 한다.

 

이렇게 데이터의 양이 커지고, type의 복잡도가 증가하면 내장된 기본 메소드로 정렬을 하는 것은 매우 비효율적인 결과를 낳을 수 밖에 없다. 그렇기 때문에 각 상황에 맞는 정렬 방식을 취해 효율적이고 빠르면서도 정확한 결과를 얻기 위해 정렬 알고리즘을 배워야 하는 것이다.

 

1. Bubble Sort

1) Bubble Sort의 특징

Bubble Sort는 수 많은 정렬 로직들 중 가장 쉽고 기초적인 정렬 로직이다. 기초적인 수준인 만큼 구현이 쉽기 때문에 주로 교육목적으로 사용된다.

 

[Big O]

• Best Case : O(n) - 이미 정렬이 다 되어 있는 경우에는 O(n)이 될 수 있다. 정렬이 잘 되었는지 점검하는 측면에서 사용 가능하다.
• Worst Case : O(n^2)
• 공간복잡도 : O(1)

[장점]

• 'IN PLACE' : 추가적인 메모리 공간을 사용하지 않기 때문에 메모리 효율성이 높다.
• 빠르게 정렬여부를 체크할 수 있다. : 다른 알고리즘으로 체크할 경우보다 Bubble Sort를 활용할 때 데이터의 정렬여부를 빠르게 체크할 수 있다.

[단점]

• 성능이 좋지 않다. 특히 데이터가 커지면 효율성은 재앙이다.

bubble sort

 

2) Bubble Sort의 로직

1) 배열의 처음부터 한 요소씩 비교를 시작한다.
2) n번째 요소와 n+1번째 요소의 크기를 비교하여, 크기가 더 작은 요소가 앞에 오도록 위치를 서로 변경해준다.
3) 배열의 맨 마지막 요소까지 2)번 작업을 반복한다.
4) 배열 1회 순회가 끝나면, 다시 처음부터 1)~3)번의 과정을 반복한다.

 

3) Bubble Sort 구현

const unsortedData = [-10, 3, 6, 2, 0, 28, -19, 25];

function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let k = 0; k < arr.length - 1 - i; k++) {
      if (arr[k] > arr[k+1]) {
        const temp = arr[k];
        arr[k] = arr[k+1];
        arr[k+1] = temp;
      }
    }
  }

  return arr;
}

bubbleSort(unsortedData);

 

• arr.length - 1 - i : 배열 전체를 1회 순회할 때마다, 가장 큰 수가 맨 뒤로 정렬이 되는 것은 보장되는 작업이다. 따라서 매 순회마다 처음부터 끝까지 순회할 필요는 없기 때문에, 정렬이 완료된 가장 마지막 요소는 제외하고 순회하기 위해 i를 추가적으로 빼준다.

 

2. Insertion Sort

1) Insertion Sort의 특징

Insertion Sort도 Bubble Sort와 마찬가지로 시간복잡도의 측면에서 효율적이지는 못하다. 하지만 Insertion Sort는 경우에 따라서 가장 빠른 정렬 성능을 낼 수도 있기 때문에 어떤 상황에서 사용 가능할지 살펴보자.

1. Data의 규모와 크기가 작은 경우
2. Data가 거의 정렬이 되어있음이 보장될 경우

위 두가지의 경우 복잡한 Quick Sort나 Merge Sort보다 오히려 Insertion Sort가 더 빠른 속도를 낼 수도 있음을 명심하자. 예를 들면 이미 정렬이 되어있는 데이터에 값을 추가한 후, 추가한 값까지 포함하여 정렬할 경우 Insertion Sort는 아주 효과적이다.

 

[Big O]

• Best Case : O(n) - Bubble Sort와 마찬가지로 정렬이 다 되어있는 경우 O(n)이다.
• Worst Case : O(n^2)
• 공간복잡도 : O(1)

[장점]

• 'IN PLACE' : Bubble Sort와 마찬가지로 메모리를 추가로 사용하지 않는다.
• 'STABLE' : 정렬 시 원본 자료의 순서가 보존됨을 의미한다. 상황에 따라서 stable한 정렬은 중요할 수 있다.

[단점]

• Bubble Sort와 마찬가지로 성능이 좋지 않다.

insertion sort

 

2) Insertion Sort의 로직

1) 배열의 처음부터 순회를 시작한다.
2) 정렬대상이 되는 각 순회의 첫번째 요소가 배열의 맨 처음 요소보다 크기가 작을 경우, 맨 앞으로 옮겨준다.
3) 그렇지 않을 경우, 배열의 두번째 요소부터 순회하면서 정렬대상이 k-1번째 index보다는 크고 k번째 index보다는 작은 위치를 찾는다.
4) 해당 위치에 정렬대상을 삽입한다.
5) 배열의 끝까지 다 돌 떄까지 2)~4)번 과정을 반복한다.

 

3) Insertion Sort 구현

const unsortedData = [-10, 3, 6, 2, 0, 28, -19, 25];

function insertionSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < arr[0]) arr.unshift(arr.splice(i, 1)[0]);
    else {
      for (let k = 1; k < i; k++) {
        if (arr[i] > arr[k-1] && arr[i] < arr[k]) {
          arr.splice(k, 0, arr.splice(i, 1)[0]);
        }
      }
    }
  }

  return arr;
}

insertionSort(unsortedData);

 

다음 글에서는 더 복잡한 알고리즘이지만 더 효율적인 Merge Sort와 Quick Sort에 대해서 정리한다.