삽입 정렬
앞에 설명한 버블 정렬 , 선택 정렬과 같이 시간 복잡도가 O(N^2)에 속하지만,
필요할 때만 위치를 바꾸기 때문에 앞에 소개한 정렬 방식들에 비하면 조금은 빠른 편이다.
일단 코드를 가지고 와서 하나하나 뜯어보고 동작을 정리하려한다.
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 answer;
}
let a = [11, 7, 5, 6, 10, 9];
console.log(solution(a));
우선 변수는 값을 담아둘 tmp 라는 변수와
스코프로 인한 에러 때문에 j 라는 변수를 사용해준다.
for (let i = 1; i < arr.length; i++) {
첫줄 i 포문이고 arr를 순회한다.
let tmp = arr[i], j;
이후 변수 tmp에 arr[i] 의 값을 담아준다. i는 1이므로 tmp = 7 이 된다.
for (j = i - 1; j >= 0; j--) {
이후 j 포문이 돌아가는데 i-1 번째부터 돌아가고 0까지 하나씩 줄어들면서 돌아간다.
if (arr[j] > tmp) arr[j + 1] = arr[j];
arr[j] > tmp 라는 조건이 달린 if문이 있는데 바로 값을 넣어서 읽어보면
j는 i-1 이기 때문에 현재 1인 i -1 = 0. 즉, 11 이 된다.
tmp 는 아까 넣어준 7이다.
11 > 7 조건이기때문에 true가 되고 ,
다음 코드가 실행된다.
arr[j + 1] = arr[j];
arr[j+1] 의 위치에 arr[j] 의 값을 할당해준다는 것이다.
j는 현재 0이므로 arr[0] , arr[j+1] 은 arr[1] 이 된다.
즉 11의 값을 7의 값에 "복사" 하는 형태가 된다.
현재까지의 배열 상태
[11, 11 , 5 , 6, 10, 9] // tmp = 7
j가 현재 0 인 상태에서 j -- 로 포문이 돌기때문에
j 포문은 false가 되며 else break 를 만나게 된다.
이후
arr[j + 1] = tmp;
j는 현재 j-1이 돼서 포문이 끝난 상태이고,
여기서 +1을 시켜주면 j[-1+1] 즉 j[0] 이 될 것이다.
0에 자리에 tmp =7 을 할당해준다는 것이다.
현재 배열 상태
[7 ,11, 5 ,6 ,10, 9] 가 된다.
이 다음 i가 1 증가한 상태로 값을 tmp에 넣고
j포문을 돌려 꾸준하게 배열에 삽입하며 정렬하는 방식이다.
