알고리즘 : 삽입 정렬(Insert sort)

삽입 정렬(Insert sort)

삽입 정렬은 마치 카드 게임에서 카드를 정렬하는 방식과 유사합니다.

• 손에 들고 있는 카드들을 순서대로 정렬된 새로운 묶음에 하나씩 올바른 위치에 삽입하는 것처럼 작동합니다.
• 배열의 두 번째 요소부터 시작하여, 그 앞의 요소들과 비교하면서 자신의 위치를 찾아 삽입하는 방식입니다.
• 시간복잡도는 평균적으로 O(n²)이지만, 거의 정렬된 배열에서는 O(n)에 가까운 성능을 보입니다.

 
 

// 삽입정렬
function insertSort(array) {
	for (let i = 1; i < array.length; i++) {
    	let currentValue = array[i];
        let j;
        for (j = i - 1; j >= 0 && array[j] > currentValue; j--) {
        	array[j + 1] = array[j];
        }
        array[j + 1] = currentValue;
    }
    return array;
}

let array = [5, 2, 4, 1, 3];
insertSort(array);

 
코드의 주요 부분 설명하면 

let currentValue = array[i];  // 현재 삽입할 값을 저장

• 현재 처리할 요소를 임시 변수에 저장합니다.

for (let j = i - 1; j >= 0 && array[j] > currentValue; j--)

 

• 현재 값의 왼쪽에 있는 모든 큰 값들을 오른쪽으로 이동시킵니다.
• j >= 0: 배열의 시작 범위를 벗어나지 않도록 합니다.
• array[j] > currentValue: 현재 값보다 큰 값들만 이동시킵니다.

 

array[j + 1] = currentValue;  // 적절한 위치에 현재 값을 삽입

• 모든 큰 값들을 이동시킨 후, 찾은 적절한 위치에 현재 값을 삽입합니다.

코드의 동작 과정

 
1) 첫 번째 반복 (i=1):
 배열 = [5, 2, 4, 1, 3]

• currentValue = 2
• 2와 5를 비교 → 2가 더 작음
• 5를 한 칸 오른쪽으로 이동 // [5, 5, 4, 1, 3]
• 2를 삽입 // [2, 5, 4, 1, 3]
• 결과: [2, 5, 4, 1, 3]

2) 두 번째 반복 (i=2):
 배열 = [2, 5, 4, 1, 3]

• currentValue = 4
• 4와 5를 비교 → 4가 더 작음 
• 5를 한 칸 오른쪽으로 이동 // [2, 5, 5, 1, 3]
• 4와 2를 비교 → 4가 더 큼
• 4를 삽입 // [2, 4, 5, 1, 3]
• 결과: [2, 4, 5, 1, 3]

3) 세 번째 반복 (i=3):

• currentValue = 1
• 1과 5, 4, 2를 순차적으로 비교
• 모든 값들을 오른쪽으로 이동
• 1을 맨 앞에 삽입
• 결과: [1, 2, 4, 5, 3]

4) 네 번째 반복 (i=4):

• currentValue = 3
• 3과 5, 4를 비교
• 5, 4를 오른쪽으로 이동
• 3을 적절한 위치에 삽입
• 최종 결과: [1, 2, 3, 4, 5]

즉, 삽입정렬은 i 인덱스 기준으로 i 보다 작은 인덱스의 위치한 값들과 순차대로 비교하며 기준 값보다 큰 값들만 이동 적절한 위치에 값을 삽입하는 정렬 방식을 말합니다.