삽입 정렬

 

 

1. 삽입 정렬

 

삽입 정렬은 다음과 같이 진행된다.

 

1. 현재 타깃이 되는 숫자와 이보다 앞에 위치하는 숫자들을 비교

2. 타깃 숫자 < 앞에 위치하는 숫자  =>  서로 교환

3. 타깃 숫자 > 앞에 위치하는 숫자 => 다음 타깃으로 이동

4. 위와 같은 방법으로 반복

 

 

시간복잡도

최선의 경우 : O(N) => 거의 정렬된 경우는 매우 효율적

최악의 경우 : O(N*N) => 역순에 가까울 수록 매우 비효율적

 

 

2. 그림으로 설명

 

다음과 같은 상황이라고 하자.

 

 

단계 1

 

첫번째 타깃은 두 번째부터 시작된다.

이때 타깃 숫자인 2보다 앞에 위치한 1이 작다.

그러면 자리 변경없이 끝이 난다.

 

 

다음 타깃으로 이동한다.

 

 

단계 2

 

두번째 타깃은 세 번째에 위치한 5이다.

앞에 있는 2가 더 작으므로 역시 자리 변경 없이 다음 타깃으로 이동한다.

 

 

 

 

단계 3

 

세 번째 타깃인 4보다 앞에 있는 5가 크므로 둘의 자리를 바꿔준다.

 

4보다 앞에 있는 2가 작으므로 다음 타깃으로 이동한다.

 

 

단계 4

 

 

 

 

이렇게 완성이 된다.

 

 

 

3. 최종 코드

 

import java.io.IOException;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		int a [] = {1,2,5,4,3};
		int size = a.length;
		
		for(int i=0; i<size; i++) {
			int target = a[i];
			
			int j = i-1;
			
			while(j>=0 && target < a[j]) {
				
				a[j+1] = a[j];
				j--;
			}
			
			a[j+1] = target;
		}
		
		System.out.println(Arrays.toString(a));
		
	}
}

 

참고 블로그 :

https://st-lab.tistory.com/179

자바 [JAVA] - 삽입 정렬 (Insertion Sort)