[Java]삽입 정렬(Insertion Sort)

*삽입 정렬(Insertion Sort)

->삽입 정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다.

->2번째 원소부터 n번째 원소부터 차례로 각 원소가 맞는 위치에 '삽입'하는 방식을 사용하며 배열을 정렬하기 때문에 삽입 정렬이라고 이름지었다.

※사람에게 어떤 대상을 정렬하라고 한다면 무의식적으로 수행하는 정렬 방식이라고 한다!

 

*삽입 정렬의 이해

->어떤 대상을 '오름차순'으로 정렬할 때 삽입 정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고, n번째 원소까지 이 방식을 반복함으로써 정렬을 진행할 수 있다. 예를 들어 [6, 2, 3, 4, 1]이라는 배열을 삽입 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

초기 배열 상태. Array[CurIndex]는 임시 변수에 저장하여 값을 기억해둔다.

 현재 선택된 원소의 앞 원소와 비교를 하며 현재 원소의 적절한 위치를 찾는 방식이기 때문에, 우선 Array[0]와 Array[CurIndex]를 비교를 하게 된다. 이때, Array[0] > Array[CurIndex]이므로 0번째 인덱스의 원소를 뒤로 미뤄버린다.

현재 대상 원소인 Array[CurIndex]의 값보다 Array[0]의 값이 크기 때문에, 해당 값을 다음 인덱스인 1로 미뤄버린다.

그렇다면 다음과 같은 상태가 되어 있을 것이다.

 이때 가장 앞 원소까지 탐색이 종료되었으므로, 최종적으로 미뤄졌던 인덱스에 현재 인덱스의 값을 '삽입'한다.

0번째 인덱스에서 미뤄지는 것이 종료되었으므로, 해당 위치에 초기에 선택했던 값을 삽입한다.

그렇다면 다음과 같은 상태가 되어 있을 것이다.

 2번째 원소에 대한 탐색이 종료되었으므로, 이번에는 3번째 원소에 대한 값을 기준으로 위 과정을 똑같이 반복해준다. 즉 초기 상태는 아래와 같아질 것이다.

초기 배열 상태. 마찬가지로 Array[CurIndex]의 값은 임시 변수에 저장하여 값을 기억해둔다.

 마찬가지로 현재 원소의 앞의 원소만을 탐색하기 때문에, Array[1]과 Array[CurIndex]의 값을 비교하게 될 것이다. 이때, Array[1] > Array[CurIndex]이므로 해당 원소의 위치를 뒤로 미뤄버린다.

해당 원소를 뒤로 미뤄버린다.

따라서 다음과 같은 상태가 되어 있을 것이다.

 다음으로 Array[0]와 Array[CurIndex]를 비교해보면 Array[CurIndex]의 값이 더 크기 때문에, 탐색을 종료한다. 탐색을 종료한 지점이 1이므로, 해당 위치에 임시로 저장해두었던 Array[CurIndex]의 값을 삽입해준다.

Array[0] < Array[CurIndex]이므로, 1번째 원소에서 탐색이 종료되고 해당위치에 기억해두었던 값을 삽입해주면된다.

 이러한 과정을 n번째 원소까지 반복해준다면 정렬이 완료된다.

 

*삽입 정렬의 구현

->쉽게 말해 2번째 원소부터 시작하여, n번째 원소까지 해당 원소의 앞 원소들과 비교하여 해당 원소가 위치해야할 자리를 찾는 과정을 구현해주면 된다.

package sort;

import java.util.Arrays;

public class InsertionSort {
	static int[] nums;

	public static void main(String[] args) {
		nums = new int[10];
		for (int i = 0; i < 10; i++) {
			nums[i] = (int) (Math.random() * 10);
		}
		System.out.println("<정렬 전>");
		System.out.println(Arrays.toString(nums));
		
		for(int i = 1; i < nums.length; i++) {
			// 현재 선택된 원소의 값을 임시 변수에 저장해준다.
			int temp = nums[i];
			// 현재 원소를 기준으로 이전 원소를 탐색하기 위한 index 변수.
			int prev = i - 1;
			// 현재 선택된 원소가 이전 원소보다 작은 경우까지만 반복. 단, 0번째 원소까지만 비교한다.
			while(prev >= 0 && nums[prev] > temp) {
				// 현재 선택된 원소가 현재 탐색중인 원소보다 작다면, 해당 원소는 다음 인덱스로 미뤄버린다.
				nums[prev + 1] = nums[prev];
				// 다음 대상 원소를 탐색한다.
				prev--;
			}
			// 탐색이 종료된 지점에 현재 선택되었던 변수의 값을 삽입해준다.
			nums[prev + 1] = temp;
		}
		
		System.out.println("<정렬 후>");
		System.out.println(Arrays.toString(nums));
	}
}

 

*삽입 정렬의 시간 복잡도

->예를들어 [5, 4, 3, 2, 1]과 같은 최악의 경우에는 각각의 탐색에서 무조건 앞의 모든 원소를 뒤로 미뤄버리는 작업을 해야하기 때문에, 시간 복잡도는 O(n^2)이다.

->이렇게 탐색을 진행하면서 원소를 뒤로 미뤄버리는 방식을 사용하기 때문에 자료구조에 따라 다른 성능을 보일 수 있다. 다만, 정렬하고자 하는 대상의 원소 수가 적다면 일반적으로 빠르다고 알려진 알고리즘보다 좋은 성능을 가지고 있다고한다. 따라서 고성능 알고리즘에서는 배열의 사이즈가 큰 경우에는 O(nlogn)정렬을 사용하다가 정렬해야 하는 부분이 작아지면 삽입 정렬로 전환하는 방식을 사용한다고도 한다. 일반적인 경우 탐색을 제외하면 삽입 정렬의 방식이 오버헤드가 매우 적기 때문이라고 한다.

※참고 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.1.3

->앞 부분에서 삽입해야할 위치를 찾는 경우, 앞 부분은 이미 정렬되어 있다는 점을 활용하여, 위치를 찾는 방법에 이진 탐색을 활용해볼 수 있다. 이 경우 최선의 경우 O(nlogn)의 시간 복잡도를 갖는다.