삽입 정렬 (Insertion Sort) 알고리즘 설명 + 예제

삽입 정렬 (Insertion Sort) 은 정렬 알고리즘 입니다. Merge Sort (합병 정렬) 이나 Quick Sort (퀵 정렬) 보다 빠른 스피드를 가지고 있거나 메모리 사용공간 효율적인 정렬 알고리즘은 아니지만 Bubble Sort (버블 정렬) 보다는 효율적이고 자바 프로그래머라면 누구나라도 기본적으로 알고 있어야 될 중요한 정렬 알고리즘 중 하나 입니다.

삽입 정렬 (Insertion Sort) 이란?

삽입 정렬을 한마디로 정의한다면 다음과 같습니다.

"리스트(집합) 를 정렬되지 않는 리스트와 정렬된 리스트의 개념으로 

나뉜후 정렬되지 않는 리스트의 아이템들을 정렬된 리스트로 

하나씩 옮긴다."

즉, 삽입 정렬을 가장 간단하게 표현 할수 있는 의사코드 (Pseudocode) 는 다음과 같습니다.

for (each item x in unsorted list U) {

     insert X into sorted list S in sorted order 

}

예제 (Example)

다음과 같은 숫자가 순서되로 들어 있는 U 라는 이름을 가진 리스트가 있다고 가정합니다.

U = {23, 42, 4, 16, 8, 15}

보다시피 리스트 U 의 크기는 6 이고 인덱스 0 에서 시작해서 5 까지 배열되어 있습니다. 

위의 리스트 U 를 삽입 정렬을 사용해서 정렬할려면 정렬된 숫자들을 저장할 리스트 S 를 따로 만들어야 합니다.

 S = {}

그리고 아이템을 U 에서 S 로 차곡차곡 옮기는거죠. 다음과 같습니다.

Iteration 0

Item to Sort: 23

U = {23, 42, 4, 16, 8, 15}

S = {23}

Iteration 1

Item to Sort: 42

U = {23, 42, 4, 16, 8, 15}

S = {23, 42}

Iteration 2

Item to Sort: 23

U = {23, 42, 4, 16, 8, 15}

S = {23, 4, 42}

S = {4, 23, 42}

Iteration 3

Item to Sort: 16

U = {23, 42, 4, 16, 8, 15}

S = {4, 23, 16, 42}

S = {4, 16, 23, 42}

Iteration 4

Item to Sort: 8

U = {23, 42, 4, 16, 8, 15}

S = {4, 16, 23, 8, 42}

S = {4, 16, 8, 23, 42}

S = {4, 8, 16, 23, 42}

Iteration 5

Item to Sort: 15

U = {23, 42, 4, 16, 8, 16}

S = {4, 8, 16, 23, 15, 42}

S = {4, 8, 16, 15, 23, 42}

S = {4, 8, 15, 16, 23, 42}

FINISH

Big-O 성능 (Performance)

삽입 정렬은 평균 O(N^2) 타임을 요구합니다. 제일 처음 정렬되지 않는 리스트를 돌리기 위해서는 루프가 필요하기 때문에 O(N) 시간이 소모됩니다. 그리고 정렬된 리스트안에서 적합한 장소에 삽입 시킬려면 또 보통 O(N) 시간이 듭니다. O(N) x O(N) = O(N^2) 이죠.

하지만 만약 리스트가 이미 정렬되어 있을경우엔 O(N) 즉 linear 시간밖에 들지 않습니다.

자바 코딩 예제(Coding Implementation Example)

package com.tutorial.sorting;

public class InsertionSortTest {
	public static void main(String[] args) {
		InsertionSortTest ist = new InsertionSortTest();
		int[] listUnsorted = new int[]{23,42,4,16,8,15};
		
	 	System.out.println("=====================================");
	 	System.out.println("\t Insertion Sort Example ");
		System.out.println("=====================================");
	 	System.out.print("Unsorted List: ");
		for(int i=0; i < listUnsorted.length; ++ i) {
			System.out.print(listUnsorted[i] + " ");
		}
		System.out.println();

		int[] listSorted = ist.getSortedListByInsertionSort(listUnsorted);
		
		System.out.print("Sorted List: ");
		for(int i=0; i < listSorted.length; ++ i) {
			System.out.print(listSorted[i] + " ");
		}
		System.out.println();

	}
	
	/**
	 * Implements the insertion sort using the array of integers
	 */
	public int[] getSortedListByInsertionSort(int[] listUnsorted) {
		if(listUnsorted.length < 2) {
			return listUnsorted;
		}
		int[] listSorted = new int[listUnsorted.length];
		// Keeps track of the number of items added to the sorted list
		int posItemLast = 0;
		listSorted[posItemLast] = listUnsorted[posItemLast];
		for(int iUnsorted = 1; iUnsorted < listUnsorted.length; ++ iUnsorted) {
			int newItemToSort = listUnsorted[iUnsorted];
			int iSorted = posItemLast;
			// Keep searching from right to left to insert new item where the new item < old item
			while(iSorted != -1 && newItemToSort < listSorted[iSorted]) {
				// Keep pushing the old item to the right by 1
				listSorted[iSorted+1] = listSorted[iSorted];
				--iSorted;
			}
			// Inserts the new item to the position that was found
			listSorted[iSorted+1] = newItemToSort;
			++posItemLast;
		}
		return listSorted;
	}
}