삽입 정렬 (Insertion sort)

모든 원소에 대해 해당 원소 앞에 이미 정렬된 배열에서 자신의 위치를 찾아 삽입하며 정렬하는 알고리즘

정렬 과정

1. 정렬할 자료를 두 개의 부분집합 S와 U로 가정한다.
   • 부분집합 S : 정렬된 앞부분 원소들
   • 부분집합 U : 아직 정렬되지 않은 나머지 원소들
2. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
3. 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 된다.
4. 부분집합 U가 공집합이 되면 삽입정렬이 완성된다.
   
   

소스 코드

void InsertionSort() {	
	int[] nums = {1000, 400, 12, -59, 328, 121, -3};
		
        // loop 1
	for(int i = 1; i < nums.length; i++) {
    
    		//loop 2
		for(int j = i-1; j >= 0; j--) {
        
        		// conditional 1
			if(nums[j] > nums[j+1]) {
				int temp = nums[j+1];
				nums[j+1] = nums[j];
				nums[j] = temp;
			} 
		}
	}
	
	System.out.println(Arrays.toString(nums));
}

loop 1: 두 번째 원소부터 마지막 원소를 의미한다.
loop 2: 현재 원소의 앞에 있는 원소들을 의미한다.
conditional 1: 두 원소를 비교하고 큰 원소를 뒤로 밀어내며 자리를 찾아간다.

시간 복잡도

최악의 경우, 삽입 정렬과 마찬가지로 O(N^2) 이다.

모두 정렬되어 있는 최적의 경우, 원소들을 한 번씩만 비교하므로 O(N) 이다. 또한, 원소를 하나씩 삽입/삭제 하는 경우에는 오버헤드가 매우 적다.

배열의 크기가 작을 때 상당히 효율적이어서 배열의 크기가 클 때는 O(nlogn) 알고리즘을 쓰다가 삽입정렬도 전환하기도 한다.

공간 복잡도

단 하나의 배열에서만 진행되므로 O(n) 이다.

장점

• 구현이 단순하다.
• 대부분의 원소가 이미 정렬된 경우 매우 효율적이다.
• 제자리 정렬(in-place sorting) 이므로 다른 메모리 공간을 필요로 하지 않는다.
• 안정 정렬(stable sort) 이다.
• 버블 정렬, 선택 정렬보다 상대적으로 빠르다.
  
  

단점

• 평균과 최악의 시간복잡도가 O(N^2) 이므로 비효율적이다.
• 버블 정렬, 선택 정렬과 마찬가지로 배열의 크기가 클수록 비효율적이다.
• 자료구조에 따라 원소를 밀어내는데 시간이 오래 걸린다.
  
  

[참고]

• 삽입 정렬(Insertion Sort)