삽입 정렬(Insert Sort)

삽입 정렬(Insert Sort)

삽입 정렬은 정렬이 되어 있는 부분집합(Sorted)과 정렬이 되어 있지 않은 부분집합(Unsorted)으로 나누어 정렬이 되어 있는 부분집합에 새로운 원소의 위치를 찾아 '삽입'하여 정렬한다.

첫 번째 원소를 정렬 되어 있는 부분집합으로 시작하고, 정렬되지 않은 부분집합에서 원소를 정렬 되어 있는 부분집합 마지막 원소부터 비교하여 위치를 찾는다.

​

평균 비교 횟수는 n(n-1)/4 이고 평균 시간 복잡도는 O(n^2)이다.

​

예시)

{57, 16, 41, 2, 50}

하나의 집합이지만 편의상 나눠서 설명.

​

1. 첫 번째 원소를 정렬된 부분집합 S로 정하고 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.

S = {57} U = {16, 41, 2, 50}

===> 16을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(16 < 57)

S = {16, 57} U = {41, 2, 50}

​

2. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.

S = {16, 57} U = {41, 2, 50}

===> 41을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(16 < 41 < 57)

S = {16, 41, 57} U = {2, 50}

​

3. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.

S = {16, 41, 57} U = {2, 50}

===> 2를 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(2 < 16)

S = {2, 16, 41, 57} U = {50}

​

4. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.

S = {2, 16, 41, 57} U = {50}

===> 50을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(41 < 50 < 57)

S = {2, 16, 41, 50, 57} U = {}

​

5. 정렬되지 않은 부분집합 U가 비었기 때문에 삽입 정렬을 종료한다.

{2, 16, 41, 50, 57}

​

프로그램 작성)

package test;

class Sort {
	public void insertSort(int[] a) {
		int i, j, temp, size;
		size = a.length;
		
		// 첫 번째 원소는 정렬된 부분집합이라 생각하고 시작하므로 1부터 시작
		for(i=1; i<size; i++) {
			temp = a[i];
			j = i;
			while(j > 0 && a[j-1] > temp) {
				// 삽입될 위치를 찾을 때 까지 한 칸씩 뒤로 밀어 자리 만들기
				a[j] = a[j-1];
				j--;
			}
			a[j] = temp;
		}
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.insertSort(a);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)