삽입정렬

• 삽입 정렬

왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소와 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법.

왼쪽 비교 대상 데이터들이 정렬 되어 있다는 가정 하에 진행

메모리가 절약되지만 자료 개수가 많아지면 성능이 매우 떨어짐

const n = [11, 7, 5, 6, 10, 9]
let arr = n 

for(let i = 0; i < arr.length; i++){
  let tmp = arr[i] 
  let j;
  for(let j = i-1; j >=0; j--){
  
  }

return arr
}

• arr[i]를 tmp에 할당 그리고 j는 i기준으로 왼쪽으로 돌면서 tmp과 비교한다.

const n = [11, 7, 5, 6, 10, 9]
let arr = n 

for(let i = 0; i < arr.length; i++){
  let tmp = arr[i] 
  let j;
  for(let j = i-1; j >=0; j--){
    if(arr[j] > tmp){
      arr[j+1] = arr[j]
    } else {
      break;
    }
  }
return arr
}

• arr[j]가 tmp보다 크다. 즉, 왼쪽 요소가 더 크면 arr[j+1]의 자리에 arr[j]를 할당하는데 arr[j+1]은 실질적으로 arr[i]의 자리.

• i=1 일 때

arr = [11, 11, 5, 6, 10, 9]

const n = [11, 7, 5, 6, 10, 9]
let arr = n 

for(let i = 0; i < arr.length; i++){
  let tmp = arr[i] 
  let j;
  for(let j = i-1; j >=0; j--){
    if(arr[j] > tmp){
      arr[j+1] = arr[j]
    } else {
      break;
    }
  }
  arr[j+1] = tmp 
}
return arr

• arr[j+1]에 tmp을 할당해서 자리를 바꾼다.

출처 : https://im-developer.tistory.com/133