삽입정렬이란?
Key값과 정렬된 리스트가 주어졌을 때,
Key값을 정렬된 리스트의 알맞은 위치에 삽입하여 하나의 정렬된 리스트를 만드는 것
동작 원리
다음과 같이 숫자 4개가 주어지고 이를 삽입정렬을 이용해 정렬한다면
5 |
4 |
3 |
2 |
1. key값을 두번째 숫자 4로 지정
5 | 4 | 3 | 2 |
2. 키값과 그 앞에 있는 값을 비교 후 키값이 작으면 자리를 바꾼다.
4 | 5 | 3 | 2 |
3. 더 이상 비교할 값이 없으므로 정렬 1회전이 끝난 것
4. 세번째 값을 key값으로 지정
4 | 5 | 3 | 2 |
5. 앞의 값과 비교 및 위치 이동
4 | 3 | 5 | 2 |
3 | 4 | 5 | 2 |
6. 이를 반복하면 모든 값이 정렬된다.
2 | 3 | 4 | 5 |
예제코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import java.util.Scanner; public class InsertionSort { /* * 삽입정렬 * Key값과 정렬된 배열이 주어졌을 때, * Key값을 정렬된 배열의 알맞는 자리에 삽입하여 정렬하는 방법 */ public static void main(String[] args) { //값을 입력받고 출력하는 부 Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] array = new int[n]; for(int i=0;i<n;i++) { array[i] = scan.nextInt(); } InsertSort(array); for(int i:array) System.out.print(i); scan.close(); } public static void InsertSort(int[] array) { for(int i=1;i<array.length;i++) { //주어진 값들 중에서 2번째 값부터 Key값으로 선정 int key = array[i]; //i번째 수를 Key값으로 설정 int j = i-1; //Key값을 기준으로 왼쪽에 있는 수부터 비교 while(j>=0 && array[j]>key) { //맨앞까지 비교했거나 key값이 왼쪽수보다 작으면 순회를 멈춤 array[j+1] = array[j]; //비교한 값을 오른쪽으로 한칸 이동 --j; } array[j+1] = key; //알맞는 key값의 위치에 저장 } } } | cs |
시간 복잡도 분석
최선의 경우는 모든 수가 이미 정렬된 상태로 수가 들어올 때이다.
이때는 수의 개수인 n의 복잡도를 가진다.
하지만 최악의 경우인 반대 순서로 정렬되어 들어온 경우에는
Key값을 옮기고 그 안에서 전부다 값들을 비교해야 하기에 n제곱을 수행 복잡도를 가진다.