[Alogrithm] 삽입 정렬 (Injection Sort)

삽입 정렬 (Injection Sort)

 삽입 정렬은, 한 배열을 '앞 배열'과 '뒷 배열'로 쪼개어 '뒷 배열'의 요소를 정렬된 '앞 배열'에 들어갈 올바른 위치를 찾아 삽입하는 정렬이다. 잘 이해가 되지 않을 수 있으므로, 하나씩 설명을 해보겠다.

 

다음과 같이 주어진 배열이 있다고 하자.

  

    
    
    
    
  
array = [3, 4, 5, 2, 1, 6, 7]

3

4

5

2

1

6

7

정렬 알고리즘 전, 주어진 배열을 다음과 같이 빨간 부분과 파란 부분으로 볼 수 있다.

빨간 부분은 이미 정렬이 된 '앞 배열',

파란 부분은 '앞 배열'에 삽입이 되기 위해 대기하고 있는 '뒷 배열'로 이해하면 좋다.

 

정렬 알고리즘은 '뒷 배열'에 들어있는 첫 번째 원소부터 시작하므로, 전체 배열로 생각하면 두 번째 요소부터 정렬 대상이 된다.

두 번째 원소 '4'는 '앞 배열'의 제일 마지막 원소인 '3'보다 크므로, 이동하지 않고 자리가 결정된다.

3

4

5

2

1

6

7

세 번째 원소 '5'는 '앞 배열'의 제일 마지막 원소인 '4'보다 크므로, 이동하지 않고 자리가 결정된다.

3

4

5

2

1

6

7

네 번째 원소를 보자. '2'는 '앞 배열'의 제일 마지막 원소인 '5'보다 작으므로 앞으로 한 칸 이동한다.

'2'는 그 앞인 '4'보다 작으므로 앞으로 한 칸 더 이동하고,

그 앞인 '3'보다 작으므로 앞으로 한 칸 더 이동한다.

따라서 앞에 아무것도 없거나, 앞의 원소보다 '2'가 더 크다면 이동을 멈추고 자리를 결정한다. 

3

4

2

5

1

6

7

3

2

4

5

1

6

7

2

3

4

5

1

6

7

2

3

4

5

1

6

7

 

이와 같은 과정을 반복하면, 삽입 정렬이 완료된다. 코드를 살펴보자.

 

삽입 정렬 파이썬 코드

	"""
	삽입 정렬 (Injection_sort)
	주어진 배열을 쪼개 정렬된 '앞 배열'과 정렬되길 대기하는 '뒷 배열'로 나우어 생각한다.
	두 번째 원소부터 앞의 완성된 배열의 자리를 찾아 넣는 알고리즘.
	"""
	array = [3, 4, 5, 2, 1, 6, 7]
	for i in range(1, len(array)):
	target = array[i]
	idx = i
	for j in range(i-1, -1, -1):
	if array[j] > target:
	array[j], array[idx] = array[idx], array[j]
	idx -= 1
	print(array)

view raw injection_sort.py hosted with ❤ by GitHub

 

 

삽입 정렬 자바 코드

	/*
	* 삽입 정렬 (Injection_sort)
	* 주어진 배열을 쪼개 정렬된 '앞 배열'과 정렬되길 대기하는 '뒷 배열'로 나우어 생각한다.
	* 두 번째 원소부터 앞의 완성된 배열의 자리를 찾아 넣는 알고리즘.
	*/
	public static void injectionSort(int[] arr){
	for (int i = 1; i < arr.length; i++){
	int target = arr[i];
	int idx = i;
	for (int j = i-1; j > -1; j--){
	if (arr[j] > target){
	int temp = arr[j]
	arr[j] = arr[idx]
	arr[idx] = temp
	idx -= 1
	}
	}
	}
	}

view raw injectionSort.java hosted with ❤ by GitHub

 

 

 

삽입 정렬 장단점

 

- 삽입정렬의 장점

Best case의 경우, O(N)이라는 좋은 시간복잡도를 가지고 있다.

비교횟수를 버블정렬에 비해 확연히 줄였다.

이미 정렬된 배열, 크기가 작은 배열에 유용하다.

 

- 삽입정렬의 단점

Worst case의 경우 O(n^2)의 시간 복잡도를 가진다.

데이터의 상태와 크기에 따라 성능의 편차가 심하다.