[알고리즘] 삽입 정렬

✅ 삽입 정렬 (Insertion Sort)

❕ 기본 개념 

- 자료 배열의 모든 요소를 차례대로 정렬 완료된 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

- 배열이 길어질수록 효율이 떨어지지만 구현이 간단함

- 숫자 비교 횟수는 최악의 경우에 1 + 2 + 3 + ... + (n - 1) ≈ n² / 2 번 비교

- 따라서 시간복잡도는 O(n²), 공간복잡도는 O(1) ☜ 추가적인 메모리 필요 X

 

 

❕ 작동 방식 

 

 

 

✔ 구현 방법 (JS) 

function insertionSort(inputArr) {
  let n = inputArr.length;
  for (let i = 1; i < n; i++) {
    // Choosing the first element in our unsorted subarray
    let current = inputArr[i];
    // The last element of our sorted subarray
    let j = i - 1;
    while (j > -1 && current < inputArr[j]) {
      inputArr[j + 1] = inputArr[j];
      j--;
    }
    inputArr[j + 1] = current;
  }
  return inputArr;
}

 

 

참고자료

Algorithms iOS app - Insertion Sort Simulation

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

https://stackabuse.com/insertion-sort-in-javascript/