삽입정렬

선택정렬(O(n^2))

• 버블정렬과 마찬가지로 기본적인 정렬
• 1번째 부터 하나씩 숫자를 선택해서 반복하면서 선택한 숫자의 위치를 찾아서 정렬하는 방식
• 즉 선택한 숫자보다 큰 숫자들은 오른쪽으로 한 칸씩 밀어내고 빈 자리에 선택한 숫자를 넣는 원리
• 이해하기 좀 복잡한 편인데 효율도 안좋아서 안쓰는게 날듯

선택한 숫자보다 큰 숫자들은 오른쪽으로 한 칸씩 밀어내고 빈 자리에 선택한 숫자를 넣는 겁니다.

function insertionSort(arr) {
  let i=1, j, temp;
  for (i; i < arr.length; i++) {
    temp = arr[i]; // 숫자를 선택
    // 선택한 숫자가 정렬할 차례 숫자보다 작은 경우만 반복
    for (j = i-1; j >= 0 && temp < arr[j]; j--) {
      // 선택한 숫자가 정렬된 숫자보다 작으면, 그 자리에 작은 숫자를 대입해버린다.
      arr[j+1] = arr[j];
      // console.log(i, j, temp, arr[j+1], arr)
    }
    // 더 작은수가 없는 경우에 선택한 숫자를 넣는다.
    arr[j+1] = temp;
  }
  return arr;
}

[5, 6, '1', 2, 4, 3] '수'는 반복이 끝나고 앞으로 땡겨와진 숫자

• i[1] j[0] temp=6 6<5 => 그냥통과,
• arr[1]=6 => 안탔으니 그대로 [5, 6, '1', 2, 4, 3]
• i[2] j[1] temp=1 1<6 => arr[2]=6, [5, 6, 6, 2, 4, 3]
• i[2] j[0] temp=1 1<5 => arr[1]=5, [5, 5, 6, 2, 4, 3]

arr[0]=1 => [1, 5, 6, '2', 4, 3]

• i[3] j[2] temp=2 2<6 => arr[3]=6, [1, 5, 6, 6, 4, 3]
• i[3] j[1] temp=2 2<5 => arr[2]=5, [1, 5, 5, 6, 4, 3]
• i[3] j[0] temp=2 2<1 => 그냥통과, [1, 5, 5, 6, 4, 3]

arr[1]=2 => [1, 2, 5, 6, '4', 3]

• i[4] j[3] temp=4 4<6 => arr[4]=6, [1, 2, 5, 6, 6, 3]
• i[4] j[2] temp=4 4<5 => arr[3]=5, [1, 2, 5, 5, 6, 3]
• i[4] j[1] temp=4 4<2 => 그냥통과, [1, 2, 5, 5, 6, 3]

arr[2]=4 => [1, 2, 4, 5, 6, '3']

• i[5] j[4] temp=3 3<6 => arr[5]=6, [1, 2, 4, 5, 6, 6]
• i[5] j[3] temp=3 3<5 => arr[4]=5, [1, 2, 4, 5, 5, 6]
• i[5] j[2] temp=3 3<4 => arr[3]=4, [1, 2, 4, 4, 5, 6]
• i[5] j[1] temp=3 3<2 => 그냥통과, [1, 2, 4, 4, 5, 6]

arr[2]=3 => [1, 2, 3, 4, 5, 6]