[Algorithm] 정렬 - 삽입 정렬(Insertion Sort)

안녕하세요. J4J입니다.

 

이번 포스팅은 정렬 알고리즘 중 삽입 정렬에 대해 적어보는 시간을 가져보려고 합니다.

 

 

삽입 정렬이란?

 

삽입 정렬은 매 회전마다 현재 인덱스의 값이 왼쪽에 존재하는 인덱스의 값보다 작을 경우 위치를 바꾸며 정렬해주는 방식입니다.

 

하지만 작지 않을 경우에는 현재 턴을 종료하여 다음 턴으로 넘어갑니다.

 

왜냐하면 이미 지나온 인덱스들은 정렬이 되어있어 특정 인덱스에서 값이 작지 않다면 왼쪽에 존재하는 나머지 값들과 비교했을 때도 작지 않기 때문입니다.

 

예를 들어 길이가 5인 배열이 있다고 가정하면 정렬되는 방식은 다음과 같습니다.

 

1-1. 1번 인덱스의 값이 0번 인덱스의 값보다 작을 시 위치를 변경합니다.

 

2-1. 2번 인덱스의 값이 1번 인덱스의 값보다 작을 시 위치를 변경합니다. 작지 않을 시 턴을 종료합니다.

2-2. 1번 인덱스의 값이 0번 인덱스의 값보다 작을 시 위치를 변경합니다.

 

.

.

.

 

4-1. 4번 인덱스의 값이 3번 인덱스의 값보다 작을 시 위치를 변경합니다. 작지 않을 시 턴을 종료합니다.

4-2. 3번 인덱스의 값이 2번 인덱스의 값보다 작을 시 위치를 변경합니다. 작지 않을 시 턴을 종료합니다.

4-3. 2번 인덱스의 값이 1번 인덱스의 값보다 작을 시 위치를 변경합니다. 작지 않을 시 턴을 종료합니다.

4-4. 1번 인덱스의 값이 0번 인덱스의 값보다 작을 시 위치를 변경합니다.

 

 

구현 코드 (Java)

 

package sorting;

import java.util.Arrays;

public class InsertionSort {
	public static void main(String[] args) {
		int intArray[] = new int[]{7, 3, 15, 11, 1};
		
		for(int i=1; i<intArray.length; i++) {
			for(int j=i; j>0; j--) { // j는 i번째 부터 좌측으로
				if(intArray[j-1] > intArray[j]) { // j값이 왼쪽 값보다 작을 경우 위치 변경
					int temp = intArray[j-1];
					intArray[j-1] = intArray[j];
					intArray[j] = temp;
				} else { // 작지 않을 경우 턴 종료
					break;
				}
			}
		}
		
		System.out.println(Arrays.toString(intArray)); // [1, 3, 7, 11, 15]
	}
}

 

 

삽입 정렬 순서

 

 

특징

 

• 구현이 쉽습니다.
• 안정 정렬(stable sort)입니다. (정렬 전과 후를 비교했을 때 동일 값들끼리 순서가 변경되지 않습니다.)
• 제자리 정렬(in-place sort)입니다. (값이 담겨있는 것을 제외하고는 추가적인 공간을 사용하지 않습니다.)
• 이미 정렬이 된 상태에서 사용할 경우 매우 빠른 속도를 가집니다.
• 선택 정렬과 비교했을 때 선택 정렬보다 더 많은 교환을 하지만 더 적은 비교를 합니다.
• 시간 복잡도가 O(N^2)입니다.

 

시간 복잡도가 O(N^2)인 이유는 최악의 경우에 n만큼 순회하는 for문들을 모두 순회해야 하고 이중 포문이기 때문에 n x n인 O(N^2)이 됩니다.

 

 

정리

 

● 삽입 정렬은 인접한 인덱스의 값을 비교하며 정렬해주는 방식

● O(N^2)의 느린 시간 복잡도에 속함

● 구현이 쉽고 느린 시간 복잡도에 의해 많이 사용되지 않음

● 어느 정도 정렬이 된 상태에 사용할 경우 빠른 속도를 가짐

 

 

 

이상으로 삽입 정렬에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.