[알고리즘] 삽입 정렬 with JS

삽입 정렬

배열의 요소들을 순차적으로 검사하면서 해당 요소가 들어갈 위치를 찾아 삽입하는 정렬 알고리즘입니다. 간단하게 설명하면,  첫 번째 요소는 이미 정렬되었다고 가정하고, 두 번째 요소(i)부터 시작하여 앞의 요소(j-1)들과 비교하면서 자신의 위치를 찾아 삽입하는 방식으로 정렬을 수행합니다.

 

즉, 배열을 순회할 때 마다 j= j-1 혹은 j-- 를 반복함으로써 정렬 대상인 key 요소와 j-1 요소 간의 크기 비교를 통해 key <arr[j-1] 이 되는 지점에 key 요소를 삽입하는 작업을 정렬이 완료 될 때 까지 반복합니다.

---

삽입정렬의 실행과정

// 1번째 인덱스를 시작으로 1번쨰 인덱스와 0번째 인덱스의 값을 서로 비교합니다.
// 이 때 0번째 요소 3은 이미 정렬되어 있다고 가정합니다.
[3, 2, 4, 1, 5]

/** 물론 정렬에 대한 가정은 확정적인 것이 아니라 비교를 위해 가정하는 것이고
 향후 j-- 을 활용하여 정렬된 요소들과의 비교도 수행합니다. */

// 0번째 값인 3보다 1번쨰 값인 2가 작으므로 2와 3의 위치를 서로 교환합니다.
[2, 3, 4, 1, 5]

// 이제는 2번째 인덱스 요소와 앞의 요소와 비교합니다. 
// 4는 2,3 보다 크므로 제자리에 정렬합니다.
[2, 3, 4, 1, 5]

// 이제 3번째 인덱스 값인 1과 앞의 인덱스의 요소들과 비교합니다.
[2, 3, 4, 1, 5]

// 2보다 작으므로 적절한 위치에 삽입합니다.
[1, 2, 3, 4, 5]

// 마지막 4번째 인덱스 값인 5도 마찬가지로 비교 합니다.
// 적절한 위치에 삽입하면서 모두 정렬 되었습니다.

---

코드

function insertionSort(arr) {
  // 배열의 길이를 저장합니다.
  const n = arr.length;

  // 배열을 순회하면서 i번째 인덱스를 기준으로 정렬합니다.
  for (let i = 1; i < n; i++) {
    // key 변수에 현재 인덱스의 값을 저장합니다.
    const key = arr[i];

    // j 변수에 i-1을 저장합니다. (key를 삽입할 위치를 찾기 위한 변수)
    let j = i - 1;

    // key보다 j번째 인덱스의 값이 크거나 같을 때까지 반복합니다.
    //j가 -1 이 되면 배열의 범위를 벗어나므로 j는 0 이상이 되도록 설정합니다.
    // key는 temp 역할과 같으며, 정렬되어야 할 값을 저장합니다.
    // 만일 arr[j] 요소가 key 요소 보다 크다면 key 요소는 arr[j] 요소보다 좌측에 위치해야 합니다.
    while (j >= 0 && arr[j] > key) {
      // j+1번째 인덱스에 j번째 인덱스의 값을 할당합니다.
      arr[j + 1] = arr[j];

      // j를 감소시켜 while 문을 반복하여 key가 들어갈 위치를 찾습니다.
      // 만일 j 가 -1이 되면 즉시 while을 탈출합니다.(해당 조건은 while 조건에 명시)
      j = j - 1;
    }

     //while 문에서 탈출하면 실행되는 코드입니다.
    // 여기서 arr[j+1] 은 앞서 while 내에서 j =j-1 이 된 상태입니다.
    // 즉, 앞서 arr[j+1]= arr[j] 를 넣은 위치 보다 앞에 있다고 이해하면 됩니다.
    // key를 j+1번째 인덱스에 할당합니다. (key가 들어갈 위치에 삽입)
    arr[j + 1] = key;
  }

  // 정렬된 배열을 반환합니다.
  return arr;
}

---

시간복잡도

• 최악의 경우 (Worst Case)

알고리즘이 최대한 긴 시간이 걸리는 경우를 의미합니다. 예를 들어, 배열이 역순으로 정렬되어 있을 때 삽입정렬 알고리즘을 사용하면, 모든 요소를 비교하고 위치를 바꾸어야 하므로, n-1 + n-2 + ... + 2 + 1 = (n^2 - n) / 2 번의 비교와 교환을 수행하게 됩니다. 따라서, 최악의 경우 시간복잡도는 O(n^2)이 됩니다.

 

*** n-1 + n-2 + ... + 2 + 1 = (n^2 - n) / 2  이 나오는 이유

결론만 말하면,

이 식은 1부터 n-1까지의 자연수를 모두 더하는 것과 같습니다. 이를 등차수열의 합 공식을 이용해서 계산하면 (첫째 항 + 마지막 항) * 항의 개수 / 2와 같습니다. 여기서 첫째 항은 1, 마지막 항은 n-1, 항의 개수는 n-1개 이므로, (1 + n-1) * (n-1) / 2 = (n^2 - n) / 2가 됩니다.  이는 수학적 공식 입니다. 

 

반복문에서 배열의 길이는 n 을 나타냅니다. 이 때 배열의 요소가 총 5개 라면 n = 5 가 됩니다. 하지만, 배열에서 요소를 비교할 때 사용되는 자연수는 4개 입니다. 다시 말해, 두 번째에 해당하는 요소 부터는 앞의 요소와 비교를 수행해야 하기 때문에, 비교에 최종적으로 비교에 사용되는  요소의 개수(혹은 비교되는 요소의 길이)는 n-1이 되는 것입니다.

 

즉, 첫 번째 요소가 비교해야하는 자연수가 1 이고, 마지막 요소가 비교해야하는 자연수가  n-1이 되므로, 이 모든 자연수를 더하면 (n^2 - n) / 2가 됩니다. 그리고 이러한 계산를 쉽게 하기 위한 것이 등차수열의 합 공식이며 앞서 결론에 언급했던 방식으로 계산이 됩니다.

-----------------------------------------------------------------------------------------------------------------------------------------------------

더 풀어서 설명하면 첫 번째 원소는 두 번째부터 마지막 원소까지와 비교하면  되므로 1개의 비교만으로 정렬할 수 있습니다  그러나 두 번째 원소는 첫 번째 원소와 비교해야 하고, 세 번쨰 원소는 첫 번째와 두 번째 원소와 비교해야 하며,  마지막 원소는 앞의 모든 원소와 비교해야 합니다.  따라서 마지막 원소는 n-1개의 원소와 비교해야 합니다. 요약하자면, 정렬 알고리즘에서는 앞의 원소와 비교하면서  정렬을 진행하기 때문에,  정렬이 진행됨에 따라 비교해야 하는 원소의 수가 증가합니다. 이에 따라 마지막 원소는 모든 앞의 원소와 비교해야 하므로, n-1개의 원소와 비교해야 합니다. 만약에 이러한 공식이 이해가 안 된다면 n에 숫자를 대입해서 하나하나 확인해보는 것도 좋은 방법이라 생각합니다.

---

• 최선의 경우 (Best Case)

알고리즘이 최소한의 시간이 걸리는 경우를 의미합니다. 예를 들어, 배열이 이미 정렬되어 있는 경우 삽입정렬 알고리즘을 사용하면, 각 요소를 비교하고 위치를 바꾸지 않아도 되므로, 비교는 n-1 번만 수행하게 됩니다. 따라서, 최선의 경우 시간복잡도는 O(n)이 됩니다.

 

• 보통의 경우 (Average Case)

알고리즘이 평균적인 시간복잡도를 가지는 경우를 의미합니다. 삽입정렬 알고리즘은 비교적 간단하고 효율적인 알고리즘이기 때문에, 보통의 경우에도 시간복잡도는 O(n^2)보다 낮을 수 있습니다.

---

공간복잡도

삽입정렬 알고리즘은 입력 배열 안에서 직접 정렬을 수행하기 때문에, 추가적인 메모리 공간이 필요하지 않습니다. 따라서, 공간복잡도는 O(1)입니다.

---

참고하면 좋은 영상

https://www.youtube.com/watch?v=iqf96rVQ8fY