[ 자바스크립트(JavaScript) ] section07 - 4 - 삽입정렬

📍 section07 - 4 - 삽입 정렬

삽입 정렬은 선택정렬과 비슷하지만 조금은 다른 방식이다. 삽입 정렬의 간략한 소개는 삽입 정렬 5분 만에 이해하기 - Gunny의 영상을 확인하자.

 

삽입 정렬은 선택 정렬보다 시간 복잡도면에서 효과적인 알고리즘인데 만약, 데이터가 거의 정렬되어있다고 가정하면 while문을 거의 수행하지 않으므로 O(N)의 시간복잡도를 보여준다. 하지만 데이터가 역 정렬(반대로 정렬)되어있다면 index 끝까지 while문을 수행하므로 최악의 경우인 O(N^2)을 나타낸다.

 

 

1. i가 1부터 시작하여 n까지 탐색한다. (left 인덱스 사용으로 인해 0부터 시작을 하지 않음)

2. temp에 arr[i]를 선언한다. (나중에 덮어 씌운 값 맨 앞에 넣을 예정)

3. left가 0보다 크거나 && 나보다 좌측에 작은 값이 있을 때만 우측 값에 현재 값을 덮어 씌운다.

4. while문이 거짓이 되면 제일 마지막으로 움직인 left+1 값에 temp를 넣는다.

 

 

728x90

 

let n = 6;
let arr = [11, 7, 5, 6, 10, 9];

console.log(solution(n, arr));

// 나의 코드
function solution(n, arr) {
    for (let i = 1; i < n; i++) {
        let cur = arr[i];
        let left = i - 1;

        while (left >= 0 && arr[left] > cur) {
            arr[left + 1] = arr[left];
            left--;
        }
        arr[left + 1] = cur;
    }
    return arr;
}

// 강의 코드
function solution(n, arr) {
    for (let i=0; i<n; i++){
        let tmp = arr[i]
        let 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;
}