2022/03/15) 4. 삽입정렬 [정렬과 그리디, 결정알고리즘]

1. 문제

<삽입 정렬>
: N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성한다. 정렬하는 방법은 삽입정렬이다.

2. 해결 방법

1. 먼저 삽입정렬은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해가며 정렬하는 방식이다.
2. i는 1번 인덱스부터 도는데, i인덱스가 정해지면 j도 돌아야 한다.(=이중for문)
   j는 i-1~0(i앞~0)까지 돈다.
3. 처음에 시작할 때 tmp = arr[i]를 해주고, arr[j] > tmp이면 arr[j+1] = arr[j]를 해주고, 작을 경우엔 break를 해준다.
4. 그 후 arr[j+1] = tmp 해준다. (만약 break되지 않고 정상적으로 됐다면 j값은 -1이 됨. j>=0이 거짓이 돼서 멈추는 것이므로!)

3. 정답

        <script>
            function solution(arr){
                let answer = arr;
                for(let i = 1; i < arr.length; i++){
                    let tmp = arr[i], j;
                    for(j = i - 1; j >= 0; j--){
                        if(arr[j] > tmp) arr[j+1] = arr[j]
                        else break;
                    }
                    arr[j+1] = tmp;
                }
                return arr;
            }
            let arr=[11, 7, 5, 6, 10, 9];
            console.log(solution(arr));
        </script>

4. 진짜 진지한 반성

하루에 하나씩 하기로 해놓고 일부러 그래서 컨셉도 1일 1알고리즘이라고 해놓고 미뤄서 한 방에 다 해버리자는 욕심때문에 알고리즘 공부를 3주째 안했다. 나는 꾸준히 해야 할 수 있는 사람이다. 다시 해보자.