삽입정렬

삽입정렬

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

1. 시작은 두번째 리스트 부터 한다. 이유는 첫번째 리스트는 하나이기 때문에 정렬이 되어있다고 본다.

2. 두번째는 temp 에 넣어두고 첫번째와 비교한다. 비교시 temp 가 작다면 첫 번째 리스트를 두번째로 이동한다. temp 는 첫번째에 삽입한다.

3. 이번엔 세번째 리스트를 temp에 넣어둔다. temp보다 큰값이 나올때까지 이동시킨다.

temp = 2

6 2 7 8 1

• 6과 temp 와 비교한다.
• temp 가 작기때문에 6을 이동시킨다.
• 6이 첫번째 이므로 temp를 첫번째 자리에 둔다.
• 그럼 2 6 7 8 1로 정렬되었다
• 다시 7을 temp에 넣는다. temp보다 큰값이 없기때문에 이동하지 않는다. 8도 마찬가지
• 1을 temp 에 넣는다.
• 8과 비교해서 temp가 작으므로 8을 다섯번째로 이동한다.
• 7도 이동한다.
• 6도 이동한다.
• 2도 이동한다.
• 1을 삽입한다.

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j;
        for (j = i - 1; (j >= 0) && (temp < arr[j]); j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}