삽입정렬 (Insertion Sort)

삽입정렬

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

삽입정렬 과정

1. 처음 초기 상태이다. 처음 루프인 i는 1부터 시작하고, i번째 원소를 저장하기 위한 tmp를 선언한다.
2. 두번째 루프인 j는 i-1부터 시작해서 0이상 일 때까지 반복한다. 이 j 루프를 돌면서 i번째 원소를 저장한 tmp를 적절한 위치에 삽입하는 방식이다. 여기서는 원소 5를 적절한 위치에 삽입한다.
3. 1, 2번 과정을 거쳐서 원소 22는 적절한 위치를 삽입하는데 그대로 있다.
4. 원소 11은 적절한 위치에 삽입한다.
5. 원소 2를 적절한 위치에 삽입한다.

설명이 많이 부실한데 코드를 보면 바로 이해할 수 있을 것이다.

삽입정렬 코드

import java.util.Arrays;

public class Ex01 {
    public static void main(String[] args) {
        int[] arr = {8, 5, 22, 11, 2};
        for (int i = 1; i < arr.length; i++) { //i는 1부터 시작
            int tmp = arr[i]; //tmp 저장
            int j; //j를 for문 바깥에도 사용하기 위해 따로 선언
            for (j = i - 1; j >= 0; j--) { //j는 i-1부터 시작
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j]; //이 때는 원소를 차례로 뒤로 밀어준다.
                } else {
                    //break를 해줘야 해당 j번째에 빠져나와서 tmp를 적절한 위치에 삽입할 수 있다.
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

삽입정렬 시간복잡도

삽입정렬 시간복잡도 역시 최악의 경우 O(N^2)이 된다.

References

• https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC