정렬 알고리즘 :: 삽입정렬(Insertion Sort)

삽입정렬 Insertion Sort

 

 

 

 

정렬된 데이터열에 자신의 위치를 찾아 삽입해 들어가는 방법이다.

이미지를 떠올려본다면, 자신이 들어갈 자리를 찾아가면서 조건에 안맞는 나머지 데이터들을 오른쪽으로 밀어내는 것과 같다.

 

 

---

~ 광고 타임 ~

---

 

예를 들어 이해해보자.

정렬되지 않은 데이터 [ 5, 1, 7, 10, 3] 이 있을 때 삽입정렬을 이용하면 다음과 같다.

 

 

5	1	7	10	3	첫째값은 비교대상이 없으므로 넘어간다.
5	1	7	10	3	1을 앞의 열과 비교하니 자리가 있다. 위치로 삽입시킨다.
1	5	7	10	3	7을 앞의 열과 비교하니 자리가 없다. 냅둔다.
1	5	7	10	3	10을 앞의 열과 비교하니 자리가 없다. 냅둔다.
1	5	7	10	3	3을 앞의 열과 비교하니 자리가 있다. 위치로 삽입시킨다.
1	3	5	7	10	정렬이 완료되었다.

설명을 덧붙여보겠다.

앞서 말한 오른쪽 밀어내는 이미지가 대표적으로 밑줄친 부분에서 나타난다.

 

위와 같이 밑줄친 [1, 5, 7, 10, 3] 값들이 있을 때, 가장 끝에 있던 3을 선택하여 바로 앞의 10과 비교한다.

3은 10보다 작으므로 자리를 만들기위해 10을 우측으로 밀어낸다.

 

그래서 밀었더니 [1, 5, 7, 자리, 10] 형태가 된다.

이번엔 한 칸 더 앞인 3번째 자리의 7과 비교를 해보니 자리에 들어갈 수 있으므로 다시 7을 밀어낸다.

 

즉, [1, 5, 자리, 7, 10]의 모양이된다.

마찬가지로 2번째 자리도 보니 3이 들어갈 수 있기때문에 5를 오른쪽으로 밀어내고,

가장 앞에 1보다 3이 크므로 밀지않고 현재 자리에 들어간다.

 

그 결과, 최종적으로 [1, 3, 5, 7, 10]의 정렬이 완료된다.

 

 

 

---

~ 광고 타임 ~

---

 

 

시간복잡도는 O(n^2)이며 버블정렬과 마찬가지로 데이터가 많아질수록 효율이 떨어진다.

하지만 삽입정렬은 정렬된 열에 삽입하고 바로 빠지기(?) 때문에 버블정렬보다 효율이 좋다고 할 수 있다.

즉, 삽입정렬은 정렬된 열일 수록 효율이 좋다.

 

시간복잡도와 그래프는 앞서 포스팅했던 '정렬 알고리즘 :: 버블소트(Bubble Sort)'를 참고하자.

 

 

 

 

JAVA 코드

package tisory.blog.it_ing;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		System.out.println(" == 아이티-잉 정렬 알고리즘 == \n");
		int[] arr = {5, 1, 7, 10, 3};
		
		fn_InsertionSort(arr);
		
	}
	private static void fn_InsertionSort(int[] arr) {
		int index=0, temp=0, cnt=0;
		
		System.out.println("#2. 삽입정렬");
		System.out.println("Input : " + Arrays.toString(arr));
		for(int i=1; i<arr.length; i++){
			temp = arr[i];
			index = i-1;
			while((index >= 0) && (temp < arr[index])){
				arr[index+1] = arr[index];
				index--;
			}
			cnt++;
			arr[index+1] = temp;
			System.out.println("STEP" + cnt+ " : " + Arrays.toString(arr));
		}
		System.out.println("Result : " + Arrays.toString(arr));
	}
}

 

결과

 

 

 

 

 

 

C/C++ 코드

 

사실 자바코드와 다를게 없지만, 그래

#include <stdio.h>

//임시로 작성한 출력함수
void printArr(int *arr, int len){
	int i=0;

	for(i=0; i<len; i++){
		printf(" %d", arr[i]);
	}
	printf("\n");
}

int main(void){
	int arr[5] = {5, 1, 7, 10, 3};
	int i, index=0, temp=0, cnt=0, len=sizeof(arr)/sizeof(int);

	printf("#2. 삽입정렬\ninput : ");
	printArr(arr, len); // 출력

	for(i=1; i<len; i++){
		temp = arr[i];
		index = i-1;
		while((index >= 0) && (temp < arr[index])){
			arr[index+1] = arr[index];
			index--;
		}
		cnt++;
		arr[index+1] = temp;
		printf("STEP%d :", cnt);
		printArr(arr, len);
	}
	printf("Result : ");
	printArr(arr, len);
		
	return 0;
}

도 내용이 빈약한 것 같아 추가해본다.

 

 

 

결과

 

 

 

 

 

끝.