삽입 정렬 (Insertion Sort)

 

삽입 정렬

삽입 정렬은 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 입니다. 

 

https://visualgo.net/en/sorting

 

선택 정렬의 순서는 다음과 같습니다.

 

1. 두 번째 자료에서 시작하여 앞의 원소들과 비교해 삽입할 위치를 정합니다.
2. 삽입될 위치가 정해지면, 뒤쪽의 원소들을 한 칸씩 뒤로 이동시킵니다.
3. 원소를 정해진 위치에 삽입합니다.

앞쪽의 원소들과 비교 후, 자신의 위치를 정하고 그 위치에 삽입하는 방법으로 정렬을 합니다.

 

시간 복잡도

최악의 경우 selection sort와 마찬가지로, $O(n^2)$의 시간 복잡도를 가집니다. 수식으로 나타내면 아래와 같습니다.

$$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$

그러나 모두 정렬이 되어 있는 경우, 한 번씩만 비교하기 때문에 $O(n)$의 시간 복잡도를 가집니다.

 

자바스크립트 코드

function insertSort(arr) {
  for(let i = 1; i < arr.length; i++){
  	let temp = arr[i];
    let left = i - 1;
    
	while(left >= 0 && arr[left] > temp) {
      arr[left + 1] = arr[left];
      left--;
    }
    
    arr[left + 1] = temp;
  }
  
  return arr;
}

console.log(insertSort([1, 5, 7, 3, 9]));

 

장점

• 버블 정렬, 선택 정렬과 마찬가지로 알고리즘 구현이 쉬우며, 제자리 정렬로 별도의 데이터 공간이 필요하지 않습니다.
• 대부분 원소가 정렬이 되어있는 경우 효율적입니다.
• 중복된 수가 있을 경우, 입력된 순서대로 정렬되는 안정 정렬입니다.

단점

• 최악의 경우 $O(n^2)$로 비효율적입니다.
• 데이터가 길어지면 길어질 수 록 비효율적입니다.

 

정리

삽입 정렬은 선택 정렬과 유사한 부분이 많습니다. n 회차 이후에 n번째 자리가 정렬되는 공통점을 가지고 있습니다. 또한, 삽입 정렬의 특징은 버블 정렬, 선택 정렬과 많은 부분이 비슷합니다. 세 정렬을 비슷한 부분이 많은 만큼 쉽게 이해할 수 있으니 한 번에 같이 공부하시면 좋을 것 같습니다. : )