📚 Insertion Sort

삽입 정렬.
정렬할 값 기준 왼쪽의 리스트가 정렬되어 있다고 가정하고, 그 속에서 들어가야 할 값을 찾는 정렬이다.

📚 Implementation

class InsertionSort {
	public static void main(String[] args) {
		int[] arr = {6, 3, 2, 5, 1};

		int idx, tmp;

		for (int i=1; i<arr.length;i++) {
			for (int j=i;j>0;j--) {
            // j번째가 넣어야 할 값이므로 j번째 값이 맞는 자리까지 역순으로 찾아감
				if (arr[j-1] > arr[j]) {
					tmp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = tmp;
				}
			}
		}
		for (int i=0;i<arr.length;i++)
			System.out.println(arr[i]);
	}
}

⌛️ Time Complexity

O(n^2). 순회가 두 번이기 때문! 각 순회는 최대 N, N-1번이므로 N^2가 된다.

Is this stable?

Stable하다. 그래봐야 붙어있는 요소끼리 교환이 일어나기 때문. 요소의 크기가 같으면 스왑이 일어나지 않으므로 stable하다.