Tag: insertion sort

앞에서부터 순서대로 정렬하여 자신의 위치에 삽입하는 방법

삽입 정렬은 배열의 앞에서부터 시작하여 자신의 앞에 있는 모든 요소와 크기 비교를 통해 자신에게 맞는 위치에 요소를 삽입한다.

다음 그림과 같은 방식이다.

3을 [6]의 적절한 위치에 삽입하고 다음으로는 5를 [3, 6]의 적절한 위치에 삽입한다. 다음으로는 1을 [3, 5, 6]의 적절한 위치에 삽입하고 이 방식으로 삽입 작업이 반복된다.

코드는 다음과 같다.

const insertionSort = (arr) => {

  for(let i=1;i<arr.length;i++){
    const checkValue = arr[i];
    let left = i-1;

    while(left>=0&&arr[left]>checkValue){
      arr[left+1] = arr[left];
      left--;
    }
    arr[left+1] = checkValue;
  }
  return arr;
}

console.log(insertionSort([6,3,5,1,9,4,8,2,7]));

다른 메모리 공간이 필요하지 않고 안정 정렬(stable sort)이며 시간 복잡도는 O(N)이다. 단점으로 최악의 시간 복잡도는 O(N^2)가 될 수 있으며 배열이 커질수록 비효율적이다.