[알고리즘] 삽입정렬(Insertion sort)

삽입정렬(Insertion Sort)

- 제자리 정렬(In-placed sorting) 알고리즘

- 카드를 정렬하는 방법과 유사

- 주어진 데이터에서 첫 번째 인덱스부터 시작해 이미 정렬된 부분에서 가장 적절한 위치를 찾아 삽입하는 방식

- 주어진 데이터의 정렬 상태에 따라 O(n)에서 O(n^2)의 시간 복잡도를 가짐

 

 

선택정렬(Selection Sort) 과정

n개의 데이터가 주어졌을 때,

 

첫번째 인덱스부터 가장 적절한 위치를 찾는다.

그림에서 체크 표시가 이미 정렬된 상태의 데이터 중 삽입이 가능한 위치가 된다

첫번째 인덱스에서는 정렬된 상태의 데이터가 없기 때문에 가능한 위치는 맨앞이 된다

 

 

두번째 인덱스를 정렬할 때,

이미 첫번째 사이클에서 정렬된 7의 앞과 뒤, 두 곳에 위치할 수 있다.

8은 7보다 크기때문에, 7의 뒤에 삽입한다.

 

 

세번째 인덱스를 정렬할 때,

1이 들어갈 수 있는 위치는 총 세 곳이 있다.

1이 이미 정렬된 값들 중 가장 작기 때문에 가능한 위치 중 맨 앞에 위치한다.

 

같은 방식으로 n번째 인덱스까지 사이클을 돌면 정렬된 상태의 데이터를 얻을 수 있다.

 

 

소스코드

package algorithm;

public class selectionSort {
	public static void main(String args[]) {
		int[] a = {7, 8, 1, 9, 4, 6};
		int min;
		int idx;
		
		for(int i = 0; i < a.length; i++) {
			min = 99999;
			idx = 0;
			for(int j = i; j < a.length; j++) {
				if(min > a[j]) {
					min = a[j];
					idx = j;
				}
			}
			int tmp = a[idx];
			a[idx] = a[i];
			a[i] = tmp;
		}
		
		for(int i = 0; i < a.length; i++) {
			System.out.printf("%d ", a[i]);
		}
	}
}