3. 삽입정렬

삽입 정렬은 도대체 어떤 정렬 방식일까요?

간단히 말하면 삽입 정렬은 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘이라고 말할 수 있습니다. 삽입 정렬도 버블 정렬과 마찬가지로 구현이 간단하여 많이 사용이 되기도 합니다.

 

버블 정렬과 선택 정렬 같은 경우 모든 요소를 매번 검사하여 정렬을 했다면 삽입 정렬은 앞의 요소들이 정렬이 되었다는 가정 하에서 해당 요소보다 큰 값들의 맨 앞에 넣어 주도록 구현되어 버블 정렬과 선택 정렬보다는 효율성이 더 좋습니다.

위 그림에서의 과정을 글로 나타내면 아래와 같습니다.

 

1. 6 과 4를 비교하여 4가 더 작으므로 6 앞으로 4를 삽입한다.

2. 6과 1을 비교하여 1이 더 작으므로 4 앞으로 1을 삽입한다.

3. 6과 7을 비교하여 정렬할 필요가 없으므로 변동 사항이 없음.

4. 7과 9 도 마찬가지

5. 9와 8을 비교하여 8이 더 작으므로 8을 9 앞으로 삽입.

 

정렬될 필요성이 있는 데이터를 뽑아 이 데이터를 적절한 위치에 삽입하는 것입니다.

이 데이터는 왼쪽에 있는 데이터들이 정렬이 되어있다고 보장할 수 있으므로 멈출 수 있는 포인트를 정해줄 수 있기에 

삽입 정렬의 비교횟수는 버블 정렬보다 조금 더 나은 면을 보입니다.

시간 복잡도는 최선의 경우 O(n)이며, 최악의 경우는 O(n^2)를 보입니다. 평균 시간 복잡도도 O(n^2)입니다.

 

삽입 정렬의 비교 횟수 = 1+2+3+...+(n-3)+(n-2)+(n-1) = n(n-1)/2

(삽입 정렬의 평균 비교 횟수는 n(n-1)/4이며, 최선의 경우에는 n-1번의 정렬이 이루어집니다.)

import java.util.Arrays;
import java.util.Scanner;

public class InsertionSort {
	

	public static void main(String[] args) {
		
		System.out.println("삽입정렬");
		
		Scanner scan = new Scanner(System.in);
		String value = scan.nextLine();
		
		
		String[] arr = value.split(" ");
		int[] array = new int[arr.length];
		
		for(int i = 0; i < arr.length; i++) {
			
			array[i] = Integer.parseInt(arr[i]);
			
		}
		
		int temp = 0;
		int j;
		
		long startTime = System.nanoTime();
		for(int i = 0; i < array.length-1; i++) {
			j = i;
			while(array[j] > array[j+1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
				
				if(j != 0) {
					j--;
				}
				
			}
		}
		long endTime = System.nanoTime();
		
		System.out.println(endTime - startTime);
		System.out.println(Arrays.toString(array));
	}

}