정렬, 삽입정렬(Insertion Sort)

1. 삽입 정렬(Insertion Sort)

오름차순 정렬을 가정하고 n개의 데이터를 정렬한다고 가정하였을때 삽입 정렬은 다음과 같이 수행됩니다.

1. arr[1]부터 arr[n]까지 배열을 순회합니다.
2. 현재 데이터값을 기준으로 그 이전 위치에 존재하는 데이터값들과 비교합니다.
3. 만약 기준이 되는 데이터값이 이전 위치에 존재하는 데이터값보다 작다면 값을 서로 교환합니다. 그러나 값이 크다면 비교를 종료합니다.
4. 0번째 위치까지 2~3과정을 반복합니다.

위 삽입 정렬 수행과정을 그림으로 표현하면 다음과 같습니다.

 

2. 삽입 정렬 코드 구현

public class InsertionSort {
	public static void sort(int[] arr)
	{
		int n = arr.length;
		
		for(int i=1;i<n;i++)
		{
			int key = arr[i];
			int j = i-1;
			
			while(j>=0 && arr[j]>key)
			{
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = key;
		}
	}
}

class InsertionSortTest {

	@Test
	void test() {
		int[] arr = {5,3,2,1,4};
		
		System.out.println(Arrays.toString(arr));
		InsertionSort.sort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

[5, 3, 2, 1, 4]
[1, 2, 3, 4, 5]

 

3. 삽입 정렬 시간복잡도

• Worst Case : 배열이 내림차순으로 정렬되어 있는 경우, O(n²)
• Best Case : 배열이 이미 오름차순으로 정렬되어 있는 경우, O(n)

 

References

[GeeksForGeeks] Insertion Sort