[Algorithm] Insertion Sort(삽입 정렬)

 

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

 

위의 네번째 강의 삽입정렬에 대한 리뷰이다.

 

 

 

삽입정렬의 경우 말 그대로 insert 를 한다.

 

 

예를 들어 배열 1, 10, 5, 8 이 있다면

 

10은  [x, 1, y] 에서 1보다 큰 수를 나타내는 y 자리에 들어갈 것이다.

 

 

다음 5의 경우 [x, 1, y, 10, z] 에서 1보다는 크고 10보다 작은 y 자리에 들어갈 것이다.

 

8 의 경우 [w, 1, x, 5, y, 10, z] 에서 5보다는 크고 10보다는 작은 y 자리에 들어갈 것이다.

 

 

 

C++ 로 소스를 작성하면

#include <stdio.h>

int main(void) {
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for (i = 0; i < 9; i ++) {
		j = i;
		while(array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}

 

위와 같다.

 

 

시간 복잡도가 모두 O(N^2) 인 선택정렬, 버블정렬, 삽입정렬 중에서 특수한 경우 삽입정렬이 가장 효율적일 수 있다.

예로는 배열이 [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 의 경우 1만 맨 앞자리에 들어가면 되므로 1회면 된다. 

 

그래서 효율성을 기준으로 내림차순 정렬시 삽입 > 선택 > 버블 로 보통 설명된다.

 

 

 

위 삽입정렬 소스를 javascript로 바꾸면

 

function insertionSort() {
    let i, j, temp;
    let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
    for (i = 0; i < 9; i++) {
        j = i;
        while(array[j] > array[j + 1]) {
            temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
            j--;
        }
    }
    console.log(array.join(", "));
}

insertionSort();

 

가 된다.

 

 

Java 의 경우

public class Sort
{
    public static void insertionSort(int[] args) {
        int i, j, temp;
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        for (i = 0; i < array.length - 1; i ++) {
    	    j = i;
            while(array[j] > array[j + 1]) {
                // 최솟값을 맨 앞으로 보냄
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                j--;
    	    }
        }
        for (i = 0; i < 10; i++) {
    	    System.out.printf("%d ", array[i]);
        }
    }
}

 

로 작성하면 된다.

 

 

다시 정리하면