[Algorithm]삽입정렬 예제(insertion sort)

안녕하세요.

이번에도 기본정렬중 하나인 삽입정렬(insertion sort) 에 대해 알아보겠습니다.

삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입? 하는 정렬입니다.

시작은 1번 인덱스로 (0번인덱스가 처음인덱스), 0번 인덱스는 정렬이 되어있다고 하고 시작을합니다.(수가 하나라면 정렬을 할 필요가 없겠죠?)

그림과 예제를 보겠습니다.

보시는 것처럼 기준이 되는 수와 앞쪽 인덱스를 비교하여 앞쪽에 기준이 되는 수보다 큰 값을가진 인덱스가 있으면 한칸 밀고 기준이되는 인덱스의 수를 넣고, 또 앞쪽인덱스와 비교하여 앞쪽 인덱스가 더 크면 한칸밀고 기준이되는 인덱스의 수를 집어넣는 방식입니다.

이렇게 비교인덱스가 -1(0이 끝이기때문) 이 되거나 기준이 되는 인덱스의 값보다 큰값이 없게되면(앞쪽은 정렬이 되어있기 때문에 0번인덱스까지 비교할 필요가없다) 정렬을 종료하고 기준을 옮깁니다.

public class InsertionSort {
	public static void main(String[] args) {
		int[] a = {254,3,213,64,75,56,4,324,65,78,9,5,76,3410,8,342,76};
		int b,j;
		for(int i = 1 ; i < a.length ; i ++) {
			b = a[i];
			for(j = i-1 ; j >= 0 && a[j] > b; j --) {
				a[j+1] = a[j];
			}
			a[j+1] = b;
		}
		
		for(int i = 0 ; i < a.length ; i ++) {
			System.out.println(a[i]);
		}
	}
}

이렇게 간단한 버블정렬,선택정렬,삽입정렬 에 대해 모두 알아보았습니다.

하지만 이 정렬들은 비교값이 많아질수록 효율이 엄청 떨어집니다.

하지만 이런 간단한 기본적인 정렬 알고리즘정도는 알아두는게 모르는것보단 좋을것같습니다.

다음번엔 좀더 효율적인 정렬 알고리즘을 알아보겠습니다.