삽입 정렬(Insertion Sort)

삽입정렬은 한 번에 한 항목씩 정렬 된 배열을 작성한다.

 

 

시간 복잡도

O(N^2)

 

장점

안정적인 정렬 알고리즘

배열이 대부분 정렬되어 있는 경우 매우 효율적

 

단점

배열 안의 요소들의 이동이 많다.

배열이 큰 경우 비효율 적이다.

 

예제 코드

const insertionSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  for ( let i =0; i< arr.length; i++){
    index = i;
    while (arr[index]!==undefined && arr[index-1]>arr[index]){
      let temp = arr[index-1];
      arr[index-1] = arr[index];
      arr[index]=temp;
      index--;
    }
  }
  return arr;
};

 

 

insertionSort 함수의 두 번째 인자로  callback 함수를 받아서 그 함수의 리턴값을 기준으로 요소들을 정렬 할 수도 있다.

 

예제 코드

const insertionSort = function (arr, transform=(item)=>(item)) {
  // TODO: 여기에 코드를 작성합니다.

  for ( let i =0; i< arr.length; i++){
    index = i;
    while (arr[index]!==undefined && transform(arr[index-1])>transform(arr[index])){
      let temp = arr[index-1];
      arr[index-1] = arr[index];
      arr[index]=temp;
      index--;
    }
  }
  return arr;
};