삽입정렬

원글 : https://www.zerocho.com/category/Algorithm/post/57e39fca76a7850015e6944a

안녕하세요. 이번 시간에는 삽입 정렬에 대해 알아보겠습니다. 알고리즘에는 많은 유형이 있지만 주로 탐색과 정렬하는 것들이 많습니다. 탐색을 하기 전에는 미리 정렬을 해야 합니다. 정렬된 자료를 탐색하는 강력한 알고리즘이 있거든요. 정렬하는 방법도 여러가지가 있습니다. 그 중에 오늘은 삽입 정렬 차례입니다.

여러 개의 섞인 숫자가 있을 때, 그 숫자를 작은 순서부터 큰 순서로 정렬하는 겁니다. 삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣습니다. 세 번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣습니다. 이렇게 끝까지 계속하면 정렬됩니다.

쉽게 설명하면 오른손에 쥔 정렬되지 않은 카드를 왼손에 정렬한다고 생각하시면 됩니다. 하나를 뽑아서 왼손에 놓고, 다음 카드는 먼저 뽑은 카드들과 비교하여 알맞은 위치에 넣어줍니다. 이렇게하면 결국 왼손에는 정렬된 카드만 남습니다.

코드로 보면 어려우니까 배열이 움직이는 과정을 쉽게 예를 하나 들어서 순서대로 봅시다. 크게 두 가지 과정이 있습니다. 첫째는 다음 숫자를 선택하는 과정이고, 둘째는 선택한 숫자를 이미 정렬된 숫자들과 비교해 알맞은 위치에 넣는 과정입니다.

[5, 6, 1, 2, 4, 3]과 같은 배열이 있습니다.

첫 번째는 넘어가고 두 번째부터 시작합니다. 숫자 6을 선택하고
[5, 6, 1, 2, 4, 3]

앞의 5와 비교하는데 5보다 크기 때문에 그냥 그 자리에 둡니다. 다음 숫자 1을 선택합니다.
[5, 6, 1, 2, 4, 3]

1은 앞의 5, 6보다 작기 때문에 5, 6 앞에 넣어줍니다. 다음 숫자 2를 선택합니다.
[1, 5, 6, 2, 4, 3]

2는 1보다는 크고, 5와 6보다는 작기 때문에 그 사이에 넣어줍니다. 다음 숫자 4를 선택합니다.
[1, 2, 5, 6, 4, 3]

마찬가지 과정으로 1,2와 5,6 사이에 넣어줍니다. 다음 숫자 3을 선택합니다.
[1, 2, 4, 5, 6, 3]

마지막으로 1,2와 4,5,6 사이에 3을 넣고, 다음 숫자가 없으므로 종료합니다.

[1, 2, 3, 4, 5, 6] 정렬이 완료되었습니다. 

이제 코드로 만들어볼까요? 배열(array)을 받는 함수(insertionSort)를 만듭시다. 일단 뽑을 숫자의 위치를 선택할 변수(i)가 필요할 것 같습니다. 그리고 뽑은 숫자 값을 저장할 변수(temp)도 필요하고요. 뽑은 숫자를 알맞은 위치에 넣을 때 사용할 변수(j)도 있어야할 것 같네요.

var insertionSort = function(array) {
  var i = 1, j, temp;
  for (i; i < array.length; i++) {
    temp = array[i]; // 새로운 숫자를 선택함
    for (j = i - 1; j >= 0 && temp < array[j]; j--) { // 선택한 숫자를 이미 정렬된 숫자들과 비교하며 넣을 위치를 찾는 과정, 선택한 숫자가 정렬된 숫자보다 작으면
      array[j + 1] = array[j]; // 한 칸씩 뒤로 밀어낸다
    }
    array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자를 넣어준다.
  }
  return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]

코드가 복잡합니다. 설명을 위해 console을 넣었습니다. 잘 보면 크게 두 과정을 반복하고 있음을 알 수 있습니다. 숫자를 선택한 후 알맞은 위치에 넣습니다. 알맞은 위치에 넣는 과정이 좀 헷갈리는데, 정렬된 숫자들 중 큰 숫자부터 비교하면서 선택한 숫자가 정렬된 숫자보다 클 때까지 반복하고, 커지면 그 사이에 집어넣습니다. 즉, 선택한 숫자보다 큰 숫자들은 오른쪽으로 한 칸씩 밀어내고 빈 자리에 선택한 숫자를 넣는 겁니다.

삽입 정렬은 성능이 뛰어난 정렬은 아닙니다. 작은 수에서만 효과적인 경우가 많습니다. 첫 번째로 배우는 이유는 간단하기 때문입니다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어넣어 다시 정렬할 때는 매우 효과적입니다. 새 원소를 처음부터 한번씩만 기존의 원소들과 비교하면 되니까요.

보통 반복문을 두 번 중첩해서 돌면 성능이 그리 좋지 않습니다. 정렬이 효과적인지 아닌지 판단하려면 복잡도라는 개념을 알아야합니다. 삽입 정렬은 다른 정렬에 비해 복잡도가 높기 때문에 효과적이지 못하다고 평가받습니다.

정렬을 평가할 때, 복잡도라는 개념을 사용한다고 했습니다. 주로 정렬하는 데 걸리는 시간의 복잡도를 따집니다. 정렬을 할 때 얼마나 시간이 걸리는 지가 중요한 데 이를 평가하는 기준으로 여러가지 표기법이 있습니다. 이것들을 다음 시간에 알아보겠습니다.