[알고리즘] - 삽입정렬(Insertion Sort)

해당 포스팅에서는 정렬 기법 중 하나인 삽입정렬에 대해 설명한 후 삽입정렬을 자바스크립트로 구현해보고자 합니다.

삽입정렬 정의

삽입정렬은 배열을 정렬된 부분(앞 부분)과 정렬 안 된 부분(뒷 부분)으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복하는 정렬기법이다.

삽입정렬 로직

배열 nums 40 10 50 90 20을 예시로 삽입정렬의 로직을 살펴보겠다.

배열 nums는 원소 40만 정렬되어있고 원소 10 이후로는 정렬 안 되어있다.
즉 정렬된 부분은 40, 정렬 안 된 부분은 10 50 90 20이다.

정렬 안 된 부분의 가장 왼족 원소인 10을 정렬된 부분의 알맞은 위치에 삽입해보자.

10은 40보다 앞이기에 40 앞에 삽입되어야 한다. 삽입정렬은 아래의 로직으로 삽입을 구현한다.

• 원소 10을 변수 x에 저장하자.
• 원소 10을 정렬된 부분의 원소인 40과 비교하자.
• 40은 10보다 작으므로 10을 40으로 바꾸자.
• 정렬된 부분의 원소가 더 이상 없으므로 원래 원소인 40을 x에 저장된 10으로 변경한다.

이러한 과정을 반복하면 오름차순 정렬된다.

삽입정렬 Javascript

input: 크기가 n인 array nums
output: 정렬된 array nums

// i = 정렬 안 된 부분의 가장 왼쪽 원소의 index
// j = i랑 값을 비교할 정렬된 부분의 원소의 index
function solution(nums) {
    for (let i=1; i<n; i++) {
        let x = nums[i];
        let j = i-1;
        while (j>=0 && nums[j] > x) {
            nums[j+1] = nums[j];
            j -= 1;
        }
        nums[j+1] = x;
    }
    return nums;
}

삽입정렬 예제

예시) 배열 A 5 25 20 10 30