Udemy - 삽입 정렬

---

삽입 정렬이란?

삽입 정렬 또한 가장 초급 수준의 정렬 알고리즘이다.
버블정렬, 선택정렬과 맥락이 비슷하지만, 그래도 이 셋중에는 가장 활용도가 높고 상대적으로 효율적인 정렬 알고리즘이라고 할 수 있다.

위의 예시에서 보이는 바와 같이, 계속 한 칸 옆의 배열을 그 앞의 배열들과 비교하여 중간에 삽입할 곳을 찾는다.

즉, 기준점 포인터를 기준으로 순회 포인터 i를 통해 계속 우측으로 이동하며 검색한다. j가 다음 대상으로 이동했을 때, 0~i의 수들을 i-- 하며 계속 숫자를 i와 비교하고, 좌측 값이 i값보다 작거나 같으면 그 값의 오른쪽에 삽입시키면 된다.

---

삽입 정렬 기본 예제

주어진 배열들을 오름차순으로 삽입 정렬하는 알고리즘을 작성하시오.

function insertion(arr) {
  // 기준 값을 저장할 currentVal 변수를 선언한다.
  let currentVal;
  // 0은 좌측에 비교할 대상이 어차피 없기 때문에 1부터 시작한다.
  for (let i = 1; i < arr.length; i++) {
    // 우선 currentVal에 현재 값을 저장해둔다.
    currentVal = arr[i];
    // j가 0에 닿을 때 까지 for문을 돌리고 j는 1씩 감소해 나간다.
    // 그리고 j를 var로 선언한 이유는 해당 for문 블록 스코프 바깥인 상위 for문에서 j값을 활용해야 하기 때문이다.
    for (var j = i - 1; j >= 0; j--) {
      // 근데 만약 currentVal이 왼쪽값보다 크거나 같으면 그 왼쪽 값들은 더 탐색할 필요가 없다.
      // 따라서 그냥 break를 해주고 반복문에 의해 j--를 해준다.
      if (arr[j] <= currentVal) break;
      arr[j + 1] = arr[j];
    }
    // 그리고 아까 전 j값 오른쪽(j+1)에 currentVal을 위치시킨다.
    arr[j + 1] = currentVal;
  }
  return arr;
}

---

삽입 정렬 시간 복잡도

보통의 경우는 $O(n^2)$의 시간복잡도를 갖는다.
하지만, 정렬이 잘 되어있는 경우에는 더 효율적으로 정렬이 수행될 수 있다.

⇒ 완전히 역순으로 정렬된 배열의 경우 최악의 시간복잡도를 보일 수 있다….!

이 링크를 참고해보면 각 정렬 알고리즘별 시간복잡도 및 효율성을 한 눈에 쉽게 확인해볼 수 있다.
Sorting Algorithms Animations

---