삽입 정렬 (Insertion Sort)

오늘은 삽입 정렬 정리를 한번 해보겠다.

 

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교를 해서, 자기 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘이다.

 

정렬 방식은 아래와 같다.

 

1. 배열의 첫번째 요소는 정렬된 상태라 가정한다.

2. 배열의 두번째 요소부터 앞에 정렬된 요소들과 차례로 비교하여 교환한다.

3. 최종적으로 해당 요소는 자신의 자리에 맞는 위치에 삽입 된다.

4. 1~3 과정을 반복한다.

 

삽입 정렬은 데이터가 많아지면 많아질 수록 성능이 저하 된다.

시간 복잡도는 O(N²) 을 따른다.

 

예제 소스 코드

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

        int[] result = insertSort(data);

        for(int num : result) {
            System.out.println(num);
        }
    }
    public static int[] insertSort(int[] data) {
        int result[] = data;

        for (int i = 1; i < result.length; i++) {
            int standard = result[i];  // 기준 값
            int compare = i - 1;   // 비교할 대상 인덱스

            while (compare >= 0 && standard < result[compare]) {
                result[compare + 1] = result[compare];   // 비교 대상 값이 크면 오른쪽으로
                compare--;
            }
            result[compare + 1] = standard;  // 기준값 대입
        }

        return result;
    }
}