삽입 정렬

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 삽입정렬입니다.

입력 설명

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력 설명

오름차순으로 정렬된 수열을 출력합니다.

입출력 예제

• 입력 : 11 7 5 6 10 9
• 출력 : 5 6 7 9 10 11

---

삽입 정렬 이란 ?

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

풀이 과정

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

나의 풀이 방법

  function solution(...arr) {
       
    for (let i = 1; i <= arr.length; i++) {
      let tmp = arr[i]; // 처음에 tmp 에는 arr[i] 를 임시 저장 

      for (let j = i - 1; j >= 0; j--) {
        if (arr[j] > tmp) {
          // arr[j] 가 tmp 보다 크면 뒤의 index 로 복사한다
          arr[j + 1] = arr[j]
          arr[j] = tmp
        }
      }
    }

    return arr;
  }

  console.log(solution(11, 7, 5, 6, 10, 9));

다른 풀이 방법

 function solution2(...arr) {
  // 0번 index의 값은 그대로 둔다        
  for (let i = 0; i <= arr.length; i++) {
    let tmp = arr[i] // 새로운 숫자를 선택함
    let j;

    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > tmp) arr[j + 1] = arr[j] // 한 칸씩 뒤로 밀어낸다.
      else break; 
    }
    arr[j + 1] = tmp; // j가 끝난 지점 바로 뒤에 tmp를 넣어주어야 한다.
  }

  return arr;
}

console.log(solution2(11, 7, 5, 6, 10, 9));

---

시간 복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 입니다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 됩니다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.

최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 됩니다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

장점

• 알고리즘이 단순합니다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 입니다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠릅니다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적입니다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다.

---

REFERENCE

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC%20(Insertion%20Sort).md#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort