Insertion Sort(삽입정렬)

1. Sorting Problem

• 입력: 숫자들의 시퀀스 A a^1,a^2,...a^n
• 출력: 입력된 시퀀스를 재정렬한 순열, b^1,b^2,...b^n,
  그러한 b^1<b^2<...<b^n
• instance: <7,10,4,5,2>
  

2. 삽입정렬

• 어떤 새로운 하나의 요소를 배열에 추가하는데 정렬되었다는 특성이 깨지지 않고 새로운 요소의 적합한 위치를 찾아서 넣어주는 알고리즘.
• 그래서 새로운 아이템의 정확한 위치를 올바르게 찾아나갈때까지 스왑을 순차적으로 수행해서 올바른 위치에 넣어주는 알고리즘
  
• 코드 구현

const insertion_sort = (arr, n) => {
  let tmp = 0;
  for(let i=1; i<n; i++) {
    for(let j=i;j>0;j--) {
      if(arr[j-1] > arr[j]) {
        tmp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = tmp;
      }
    }
  }
  return arr;
}

-시간복잡도: best: O(N) average, worst: O(N^2)

참고

• 인공지능을 위한 알고리즘과 자료구조(삽입정렬 편)