[Algorithm] 정렬(2) - 삽입 정렬 with Java

삽입정렬

데이터를 하나씩 확인해가며 들어갈 자리 찾아가서 들어가겠다!

 

위의 말 그대로다. 삽입 정렬이라고 불리는 이유는 특정한 데이터를 적절한 위치에 '삽입'한다는 의미이다.

선택정렬이 가장 작은 데이터를 찾기 위해 데이터들을 일일이 비교한 뒤 스왑했다면, 삽입 정렬은 지금 데이터를 어디에 넣어야 할지 적절한 위치를 찾고 스왑해준다. 그렇기에 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.

삽입 정렬의 특징은 데이터가 거의 정렬 되어 있을 때 효율적이다!!

 

삽입정렬

빨간색 동그라미 -> 정렬된 부분들

파란색 부분 -> 적절한 위치에 넣어줘야 할 데이터

빨간색 체크 -> 적절한 위치

검은색 체크 -> 들어갈 수 있는 부분

 

1. 삽입 정렬의 경우 첫 번째 데이터는 정렬되어 있다고 가정하고, 두 번째 데이터 부터 위치 찾기에 들어간다.

1부터 위치를 찾는데 자기보다 큰 데이터가 나오면 자리를 바꿔주고, 작은 데이터가 나오면 그 자리에서 멈춘다.

즉 3이 1보다 크기 때문에 1과 3을 바꿔준다!

 

2.  다음 데이터인 5의 경우 3보다 크기 때문에 그자리에 멈춘다.

 

3. 다음 데이터인 2의 경우 5, 3 보다 작고 1보다 크기 때문에 1 앞에서 멈춘다.

 

4. 마지막 4의 경우 5보다 작고 3보다 크기 때문에 3과 비교한 그 시점에 멈춘다.

 

시간복잡도

	최선	평균	최악
삽입정렬	O(N)	O(N^2)	O(N^2)

 

삽입 정렬의 경우 데이터들이 거의 정렬되어 있을 경우 O(N)의 속도로 빠르다!

하지만 선택 정렬과 같이 이중 반복문으로 이루어지기 때문에 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

 

특징 - 안정성 & 제자리 정렬

제자리 정렬

삽입 정렬의 경우 기존 배열 그대로 사용하기 때문에 추가적인 메모리가 필요하지 않는다.

 

안정성

앞에 있는 데이터가 클 때만 바꿔 주기 때문에 선택 정렬처럼 불안정하지 않다.

코드

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args){
        int[] array = {3,1,5,2,4};

        for(int i=1; i < array.length; i++){
            for(int j =i; j > 0; j--){
                if(array[j] < array[j-1]){
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}