[Sort] 삽입정렬 (Insert Sort)

삽입정렬(Insert Sort)

삽입정렬은 정렬한 부분과 정렬하지 않은 부분을 나눈 후 정렬할 대상인 대상을 정렬하지 않은 부분에서 차례대로 꺼내 정렬한 부분의 요소들과 차례대로 비교를 하면서 자신이 삽입될 인덱스를 찾는다. 이 과정에서 정렬된 부분의 요소들이 현대 정렬대상보다 클 경우 한칸씩 뒤로 밀리면서 정렬대상이 들어갈 공간을 마련해준다. (오름차순인 경우)

자 말로하니까 어렵다. 한 단계씩 그림으로 설명해보자.

파란색은 이미 정렬된 영역이라고 하자. 빨간영역은 정렬되지 않은 영역이다.

삽입정렬은 기본적으로 0번째 요소는 정렬된 것이라 가정하고 시작한다. 

우선 1회전 과정을 살펴보자. 0번째 요소는 정렬됐다고 가정했으니, 1번째 요소 값이 정렬할 대상이다. 

 

Temp에 1번째 요소 값인 2를 임시저장한다.

다음 정렬된 영역 안에 있는 요소 하나하나를 방문하면서 Temp와 비교하여 Temp가 더 작을 경우 해당 index 첨자부터 정렬대상의 끝인 요소까지 모두가 한칸씩 밀린다. 또 더 이상 비교할 요소가 없을 경우 (index가 0이 될 때가 이제 더 이상 비교할 것이 없다는 것이다.) 까지 계속 이 과정을 반복한다. 이제 모두 정렬된 영역에 있는 요소들과 Temp가 비교를 다 하면, Temp가 진짜로 들어갈 index요소가 나올 것이다. 

이제 그 인덱스에 Temp값으로 넣는다. 

다음 2회전인 경우 

2번째까지 정렬됐으니, 2번째 요소인 3을 Temp에 임시저장을 한다. 

다음 정렬된 영역 안에 요소들에 접근하여 Temp보다 큰 값이 있을 경우 해당 요소부터 정렬된 요소 영역의 끝까지 한 칸씩 뒤로 옮긴다.

여기서는 1번째 요소 5번이 Temp보다 크기 때문에 한칸 뒤로 이동했다. 다음 0번재 요소인 2값을 Temp와 비교해보니 Temp가 더 크다. 

그렇다면 Temp의 위치는 0번째 바로 뒤인 첨자에 삽입된다. 이런식으로 정렬되지 않은 영역에 있는 요소들을 정렬된 영역 안에 모두 삽입 할 경우 자연스럽게 정렬이 된다. 

이와 같은 원리로 구현한 삽입정렬(Insert Sort)의 코드이다. 필자는 while문을 사용했다. for문으로 가능하다.

package Sort;

import java.util.Arrays;

public class InsertSort {

	public static void main(String[] args) {
		int[] array = {5,3,4,7,6,2,1};
		System.out.println("Before   : "+Arrays.toString(array)+"\n");
		insertSort(array);
		


	}

	private static void insertSort(int[] array) {
		int temp = 0;
		int j = 0;
		
		for(int i=1; i<array.length; i++){
			temp = array[i]; // 삽입대상 임시 저장.
			j = i; //index 임시저장
			while(j > 0 && temp < array[j-1]){ //삽입대상이 정렬된 대상들보다 작은 경우가 있는 경우 
				array[j] = array[j-1]; //밀기
				j--; //다음 비교를 위해 인덱스 이동
			}
			array[j] = temp; //최종으로 삽입될 위치에 삽입대상 삽입
			System.out.println((i)+"회전 select sort result : " + Arrays.toString(array));	
			
		}
	}

	
}

최적의 경우는 미리 정렬이 되어 있는 경우이다.  이 때는 O(n)의 복잡도이며,

최악의 경우는 역순으로 정렬된 경우이다. 이 때는 O(n^2)의 복잡도를 지닌다. 

but 삽입 정렬 알고리즘의 평균 비교 및 이동 횟수는 최악의 경우인 O(n^2)와 같다. 

왜냐면 상한을 기준으로 하는 Big O notation의 기준은 최악의 경우로 판단하기 때문이다.

공간복잡도는 하나의 배열에서만 sorting하기 때문에 O(n)이다.

또한, 데이터량이 8~20개 정도로 유지되는 경우 가장 빠른 정렬알고리즘이 될 수 있다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)