삽입정렬

삽입 정렬은
배열의 두 번째 요소부터 루프를 시작한다
선택한 요소를 이전에 있는 요소들과 비교하면서
선택한 요소보다 작다면 뒤에 위치시킨다
선택한 요소보다 크다면 앞에 위치시킨다

[2,1,9,76,4] 배열을 정렬해보자

1. [2,1,9,76,4]
   1은 2보다 작으니 앞으로 위치시킨다
2. [1,2,9,76,4]
   9는 2보다 크니 뒤에 위치시킨다
3. [1,2,9,76,4]
   76은 9보다 크니 뒤에 위치시킨다
4. [1,2,4,9,76]
   4는 2보다 크니 뒤에 위치시킨다

이런식으로 정렬이 된다

코드로 살펴보자

function insertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let currentValue = arr[i]
        let j;
        for(j = i - 1; j >= 0 && arr[j] > currentValue; j--){
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentValue
    }
    return arr;
}

첫 번째 루프이다
첫 번째 루프는 두 번째 요소부터 돌아야 하니 i의 초깃값은 1로 둔다

비교 대상인 값을 currentValue 변수에 할당해 준다
currentValue의 이전의 값들과 비교를 해야 하니 루프를 하나 더 생성해 준다

두번째 루프이다 j는 i-1값을 가진다
루프 조건은 j가 0보다 크거나 같아야 하고, arr[j]는 currentValue보다 커야 한다
j는 루프 밖에서로 사용해야하니 밖으로 꺼내주었다

두 번째 루프 조건에 해당한다면
j의 위치보다 +1 위치에 j의 값을 넣어둔다

그 후에 arr[j+1] 위치에 currentValue값을 넣어준다

여기서 조금 헷갈릴 것 같다

어떻게 움직이는지 보면 쉽게 이해할 수 있을 것이다

예를 들어 [1,2,9,76,4] 배열이고
현재 i는 마지막 index이다
그러므로 currentValue는 4이다
두 번째 루프를 실행해보자

1. j는 i -1이므로 76과 currentValue인 4를 비교한다
   76은 4보다 크기 때문에 두 번째 루프 조건을 충족하여 로직을 실행시키게 된다
   arr[j+1] 자리에 arr[j]를 할당한다
   그러면 값은 다음과 같다
   [1,2,9,76,76]
   그다음 루프로 가자

2. j는 9를 가리킨다 9는 currentValue인 4보다 크기 때문에 루프 조건에 충족하여 로직을 실행시킨다
   arr[j+1] 자리에 arr[j]를 할당한다
   [1,2,9,9,76]
   그다음 루프로 가자

3. j는 2를 가리키고 있다 2는 currentValue인 4보다 작기 때문에 루프 조건에 충족하지 않아 다음 줄로 간다
   arr[j+1]에 currentValue를 집어넣어 준다
   j는 현재 2를 가리키고 있고 index +1을 하게 되면 2 다음인 9를 가지고 있는 index에 currentValue인 4를 넣어준다
   결과는
   [1,2,4,9,76]
   나온다