삽입정렬

삽입 정렬이란

현재 비교하고자 하는 타깃과 그 이전의 배열들을 비교하며 자리를 교환하는 정렬 방법입니다.

 

 

특징

데이터를 비교하며 찾기 때문에 비교 정렬이며, 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬입니다.

 

---

사용법

1. 현재 타깃이 되는 숫자와 이전 위치에 있는 숫자들을 순차적으로 비교한다.
2. 타겟이 이전의 숫자보다 작은 경우 교환해준다.
3. 1~2 반복해준다.

https://en.wikipedia.org/wiki/Insertion_sort

public int[] solution(int N, int[] arr){
    for (int i = 1; i < N; i++) {
        int temp = arr[i], j; 
        // j가 두 번째 for문 밖에 있기 떄문에 선언을 해줘야 한다.

        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > temp) arr[j + 1] = arr[j]; // 한 칸씩 왼쪽으로 이동 
            else break; // 더 이상 비교 할 필요가 없음
        }
        arr[j + 1] = temp;
    }
    return arr;
}