삽입 정렬 Insertion Sort

Intro::

삽입 정렬에 대해 알아보자.

정의

Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다. 해당 인덱스의 수를 위치에 맞게 이동시켜준다고 생각하면된다.

2번째 index 값을 tmp에 저장한다.

tmp과 이전에 있는 원소들을 비교하며 삽입해나간다.

'1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

시간 복잡도

💡

최악의 경우 n(n-1)/2 ⇒ O(n^2) 이다. 하지만, 모두 정렬이 되어있는 경우 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

Code



package algorithm;

import java.util.*;

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

		for (int idx = 1; idx < arr.length; idx++) {
			int tmp = arr[idx];
			int prev = idx - 1;
			while (prev >= 0 && arr[prev] > tmp) {
				arr[prev + 1] = arr[prev];
				prev--;
			}
			arr[prev + 1] = tmp;
			System.out.println(idx + "회전: " + Arrays.toString(arr));
		}
	}
}

/*
0회전: [2, 1, 6, 5, 4, 3]
1회전: [1, 2, 6, 5, 4, 3]
2회전: [1, 2, 6, 5, 4, 3]
3회전: [1, 2, 5, 6, 4, 3]
4회전: [1, 2, 4, 5, 6, 3]
5회전: [1, 2, 3, 4, 5, 6]
*/

삽입 정렬 Insertion Sort

Intro::

정의

시간 복잡도

Code

References::