Tag: 삽입정렬

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

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

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

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)가 될 수 있으며 배열이 커질수록 비효율적이다.