[javascript] Insert Sort !

포스팅 전 주저리 : 여자친구가 어제 아이패드 프로 1세대 중고를 구입했다. 구성도 알차게 있었는데, 내가 사용하는 6세대보다 훨씬 좋아보인다 ㅜ.ㅜ 나도 열심히 공부하고 돈 벌어서 모든 애플제품을 프로로 구입하는 프로앱등이가 될거다. ! 빠샤

 

삽입정렬이란 ?

배열의 1번째 index부터 배열을 순회하며 자신보다 높은 데이터 앞에 해당 key의 데이터를 넣는 정렬 알고리즘이다. 

 

시간 복잡도는 O(n2) 이며 안정 정렬 알고리즘이다. 

 

삽입정렬이 일어날 때 내부 

 

1. 빨간글씨 key의 아이템이 전과 key 의 전 아이템과 비교한다. 

 

2. key의 아이템이 작다면 왼쪽 방의 아이템들과 비교해서 작을때까지 배열을 이동하여 key의 아이템을 삽입한다.

 

1번째 인덱스 value = 2;

[6,2,4,7,5,2] // 6과 2를 비교해 2보다 큰수가 없거나 방 번호가 -1 이 되지 않을때까지 이동한 후 삽입한다. 

 

결과

[2,6,4,7,5,2]

 

2번째 인덱스 value = 4;

 

[2,6,4,7,5,2] // 6과 4 비교. 2전까지 이동 후 삽입

 

결과

[2,4,6,7,5,2]

 

3번째 인덱스 value = 7;

 

[2,4,6,7,5,2] // 6보다 크므로 생략.

 

4번째 인덱스 value = 5;

 

[2,4,6,7,5,2] // 7과 5비교 5가 더 작으므로 4전 까지 이동 후 삽입

 

결과

[2,4,5,6,7,2]

 

5번째 인덱스 value는 2;

 

[2,4,5,6,7,2] // 7과 2 비교 2가 더 작으므로 2 전까지 이동 후 삽입

 

결과

 

[2,2,4,5,6,7]  

예제 

 

function insertSort(array){

    let key = 1;
    while(key < array.length){
        temp = array[key];
        prevent = key - 1;
        while(prevent >= 0 && array[prevent] >= temp){
            array[prevent + 1] = array[prevent];
            prevent--;
            console.log(array);
        }
        array[prevent+1] = temp;
        key++; 
    }
    return array;
}

let array = [2,5,4,8,6,0,3,6,7]

console.log(insertSort(array));