삽입 정렬

• 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하여 정렬
• 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적
• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸지만 삽입 정렬은 그렇지 않다
• 자신보다 작은 값을 만나면 그 자리에서 멈춘다
• 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자신보다 작은 데이터를 만났다면 그 앞의 데이터들은 상관없이 그 자리에서 멈추면 된다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면, 매우 빠르게 동작한다.
  
  위 이미지에서 검정색 박스가 옮겨지는 것은 빨간박스와 위치를 교환한다고 생각하면 된다.

예시)
let array = [5,7,9,0,3,1,6,2,4,8];
let num = array.length;

for(let i = 1; i < num; i++){
  for(let j = i; j > 0; j--){
    if(array[j-1] > array[j]){
      let temp = array[j-1];
      array[j-1] = array[j];
      array[j] = temp;
    }
  }
}

console.log(array);
//출력: [0,1,2,3,4,5,6,7,8,9]

시간 복잡도

• 2중 반복문이 사용되었으므로 O(N^2)이다
• 최선의 경우 O(N)의 시간복잡도를 가진다
  
  

참고: Wikimedia Commons