삽입정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 이다

      function solution(arr) {
        for (let i = 1; i < arr.length; i++) {
          const currentNumber = arr[i];
          let j;//j for문 밖에서도 j사용하기 위해서 선언해준다
          for (j = i - 1; j >= 0; j--) {
            if (arr[j] > currentNumber) arr[j + 1] = arr[j];
            //tem을 끼워넣기 전에 한칸씩 땡겨준다고 생각하면 된다
            else break;
          }
          arr[j + 1] = tem; // break일때는 해당 j || 0번 index까지 비교했을떄는 j는 -1이 된다
        }
      }

삽입정렬의 메인컨셉

for 문을 돌 때 해당 i 앞은 정렬되어 있고 해당 arr[i] 를 어디에 삽입할 것인지 정해주는 것

생각의 흐름

arr[i]를 currentNumber라고 하겠다

1. currentNumber보다 앞의 index들을 돌면서
   arr[j] > currentNumber 이면 (앞의 숫자가 뒤의 숫자보다 크면)
   arr[j+1] = arr[j] (자리 확보 위해 자기자신뒤 자신을 복사)

2. 원래자리는 다음 for문을 돌 때
   arr[j] > currentNumber보다 크면 arr[j]로
   작다면 currentNumber로 대체 될 것이다

3. 만약 계속해서 arr[j] > currentNumber 일 경우
   arr[0] 까지 비교해 주는데 arr[0]>currentNumber일 경우 arr[1]=arr[0] 으로 for문은 끝나게 되고

• (currentNumber 삽입할 arr[0]을 위한 자리를 남겨놓는것)
  j=-1이 되어 결국 arr[j+1] = arr[0]이 되고 currentNumber는 arr[0]에
  삽입되게 된다

4. else 일경우 (arr[j] <= currentNumber) break 하는 이유는 앞은 정렬되 있기 때문에 j index앞에는 arr[j]보다 큰 수가 없기 때문에 더 볼 필요가 없이 break를 하고 currentNumber를 j+1에 삽입하면된다
   -break했을 때는 j--가 일어나지 않는다

출처 자바스크립트 알고리즘 문제풀이