삽입 정렬(Insertion Sort)

이번에 배워볼 정렬 알고리즘은 삽입 정렬(Insertion Sort)이다.

삽입 정렬은 손안의 카드를 정렬하는 방법과 유사하다. 새로운 원소를 기존에 정렬된 원소 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다.

 

삽입 정렬은 비교적 많은 레코드들의 이동을 포함하기 때문에 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않음을 알 수 있다.

반면, 안정한 정렬 방법으로서 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 또한, 삽입 정렬은 대부분의 레코드가 이미 정렬되어 있는 경우에는 매우 효율적일 수 있다.

삽입 정렬(Insertion Sort)의 시간 복잡도는 O(N^2)이다.
다만, 리스트가 이미 정렬되어 있는 상태라면 O(N)의 시간복잡도를 가진다.

 

 

삽입 정렬을 Java로 구현한 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {
		int[] num = {5, 3, 1, 2, 4};
		
		num = insertion_sort(num.length, num);
		for (int k : num) {
			System.out.print(k + " ");
		}
	}
	
	public static int[] insertion_sort(int n, int[] num) {
		for (int i = 1; i < n; ++i) {
			int key = num[i];
			int j = i - 1;
			
			//정렬된 배열은 0부터 i-1까지이므로 i-1부터 역순으로 조사한다.
			//j >= 0이며, j의 원소가 Key보다 크다면 한칸 앞으로 옮겨준다.
			for (; j >= 0 && num[j] > key ; --j) {
				num[j + 1] = num[j];
			}
			
			//for문을 탈출했다는 것은 j번째 원소가 Key보다 작다는 뜻이기 때문에 j + 1의 배열에 Key값을 넣어준다.
			num[j + 1] = key;
		}
		return num;
	}
}