삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

• 해당 순서의 배열 값을 기존의 배열에 올바른 위치를 찾아 삽입한다.
• 2번째 배열의 값부터 앞쪽의 배열의 값들과 비교하여 삽입할 위치를 정한 후 나머지 값을 한칸씩 뒤로 옮기는 알고리즘이다.
• 최선의 경우 O(N)이라는 빠른 효율성을 가지고 있다. 

장점

• 구현하기 쉽다.
• 정렬된 배열이라면 비교와 교환을 적게 하기 때문에 효율적일 수 있다.
• 배열 안에서 교환방식으로 다른 메모리 공간을 필요로 하지 않는다. 

단점

• 최악의 경우 많은 값들의 이동을 필요로한다.
• 배열의 길이가 길고 비교할 값이 많다면 비효율적이다.

CODE

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

console.log(insertionSort([6,4,13,2,1]))

설명

function insertionSort(arr) {
    var store = 0;
    for(var i=0; i<arr.length; i++) {
      console.log(arr)
      console.log(`배열 ${i}번째 인덱스 탐색시작!!!`)
      console.log(" ")
      store = arr[i]
      for(var j=i-1; j>-1 && arr[j]>store; j--) {
        arr[j+1] = arr[j]
        console.log(`${i}번째 값 ${j}번째 위치로 삽입`)
        console.log(arr, i, j)
      }
      console.log("끝!!!")
      console.log(" ")
      arr[j+1] = store;
    }
    return arr
}

console.log(insertionSort([6,4,13,2,1]))
// console.log(insertionSort([1,2,3,4,5]))

// [ 6, 4, 13, 2, 1 ]
// 배열 0번째 인덱스 탐색시작!!!
// 끝!!!
// 
// [ 6, 4, 13, 2, 1 ]
// 배열 1번째 인덱스 탐색시작!!!
// 
// 1번째 값 0번째 위치로 삽입
// [ 6, 6, 13, 2, 1 ] 1 0
// 끝!!!
// 
// [ 4, 6, 13, 2, 1 ]
// 배열 2번째 인덱스 탐색시작!!!
// 끝!!!
// 
// [ 4, 6, 13, 2, 1 ]
// 배열 3번째 인덱스 탐색시작!!!
// 
// 3번째 값 2번째 위치로 삽입
// [ 4, 6, 13, 13, 1 ] 3 2
// 3번째 값 1번째 위치로 삽입
// [ 4, 6, 6, 13, 1 ] 3 1
// 3번째 값 0번째 위치로 삽입
// [ 4, 4, 6, 13, 1 ] 3 0
// 끝!!!
// 
// [ 2, 4, 6, 13, 1 ]
// 배열 4번째 인덱스 탐색시작!!!
// 
// 4번째 값 3번째 위치로 삽입
// [ 2, 4, 6, 13, 13 ] 4 3
// 4번째 값 2번째 위치로 삽입
// [ 2, 4, 6, 6, 13 ] 4 2
// 4번째 값 1번째 위치로 삽입
// [ 2, 4, 4, 6, 13 ] 4 1
// 4번째 값 0번째 위치로 삽입
// [ 2, 2, 4, 6, 13 ] 4 0
// 끝!!!
// 

// 결과!!!!
// [ 1, 2, 4, 6, 13 ]