삽입 정렬 (Insertion Sort)

1. 개요

• 선택 정렬과 유사하지만 더 효율적인 알고리즘이다.
• 정렬할 원소를 선택하고 앞의 원소들과 비교하여 알맞은 위치에 삽입한다.
• 이미 정렬되어 있는 경우, O(N)의 시간복잡도를 가진다.

---

2. 특징

• 구현이 단순하다.
• 제자리 정렬이다.
• 안정 정렬이다.
• 시간복잡도: O(N^2) / 최선의 경우 O(N)
• 다른 O(N^2) 알고리즘에 비해 빠르다.

---

3. 코드

import java.util.Arrays;

public class InsertionSortTest {

	public static void main(String[] args) {
		int[] nums = { 3, 2, 7, 5, 11, 12, 1 };

		insertionSort(nums);

		System.out.println(Arrays.toString(nums));
	}

	private static void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int curr = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j] > curr) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = curr;
		}
	}
}