[Algorithm] 삽입 정렬

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 삽입 정렬

정의

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

- 앞쪽의 원소들이 이미 정리되어 있다고 가정하고 뒤쪽에 있는 원소를 적절한 위치에 삽입한다.

예시

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	int n=10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        for (int i=1; i<n; i++) {
        	for (int j=i; j>0; j--) {
	        	if (arr[j] < arr[j-1]) {
    	        	int temp = arr[j];
        	        arr[j] = arr[j-1];
            	    arr[j-1] = temp;
            	}
            	else break;
        	}
    	}
    	for (int i=0; i<n; i++) {
    		System.out.print(arr[i] + " ");
    	}
	}
}

시간 복잡도

- O(N^2)

- 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

- 최선의 경우 (ex, 이미 정렬이 다 되어 있는 경우) O(N)의 시간 복잡도를 가진다

- 최악의 경우 : 오름차순으로 정렬되어 있는 수를 내림차순으로 바꾸는 경우 (하나도 정렬이 되어 있지 않은 경우)