삽입 정렬

📌 삽입 정렬(Insertion sort)

한 번에 하나의 항목을 올바른 위치에 삽입해서 배열의 정렬된 부분을 점진적으로 구축함.

• 시간 복잡도 :
  평균적인 랜덤 데이터의 경우 -> O(n^2)
  거꾸로 정렬된 경우가 최악의 케이스 -> O(n^2)
  거의 정렬된 데이터의 경우 가장 좋음 -> O(n)

삽입 정렬 과정 애니메이션으로 보기
https://visualgo.net/en/sorting?slide=1

예제

배열 오름차순 정렬하기

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

insertionSort([2,1,9,76,4])

과정 살펴보기

2 1 9 76 4  currentVal = 1 
2 2 9 76 4  j = 0, arr[1] = 2
1 2 9 76 4  j = -1 (j=0에서 j-- 되었으므로 -1이다.), arr[0] = 1

1 2 9 76 4  currentVal = 9
1 2 9 76 4  j = 1 일 때, 2<9, j = 0 일 때, 1<9 이므로 반복문이 실행되지 않음.
1 2 9 76 4  j = 1 (반복문이 실행되지 않아 j--가 안되므로), arr[2] = 9 로 변화가 없다.

1 2 9 76 4  currentVal = 76
1 2 9 76 4  j = 2,1,0 일 때, 모두 76보다 작으므로 반복문이 실행되지 않음.
1 2 9 76 4  j = 2 (반복문이 실행되지 않아 j--가 안되므로), arr[3] = 76 으로 변화가 없다.

1 2 9 76 4  currentVal = 4
1 2 9 76 76 j = 3 일 때, arr[4] = 76
1 2 9 9 76  j = 2 일 때, arr[3] = 9
1 2 9 9 76  j = 1 일 때, currentVal 보다 작으므로 반복문이 실행되지 않음
1 2 4 9 76  j = 1 이므로 arr[2] = 4

결과 : 1 2 4 9 76

📌 버블, 선택, 삽입 정렬 비교

• 세 정렬은 거의 비슷하다.
• 모두 평균적인 시간 복잡도가 O(n^2)이고, 공간 복잡도가 O(1)이다.
• 데이터 집합이 작은 경우 효과적이다.
• 버블정렬과 삽입정렬은 주어진 데이터가 거의 정렬되어 있을 때 효율적이다.