삽입 정렬(Insertion Sort)

개념

정렬을 진행할 원소의 index(a)보다 작은 곳(0~a-1)에 있는 원소들을 탐색하고
알맞은 위치에 삽입하여 정렬하는 알고리즘입니다.
구현이 간단하다는 특징이 있습니다.

 

로직

오름차순 정렬 기준
1~N-1번째 인덱스를 순차적으로 key로 두고
key-1 ~ 0의 인덱스를 감소순회하면서
만약 arr[현재의 값] > key 라면, arr[현재의 값+1] = arr[현재의 값]을 넣어줍니다.
그렇지 않다면, 순회를 종료합니다.
순회가 끝나고 난 후, arr[마지막 위치 + 1] = key 값으로 갱신합니다.

 

코드

자바로 작성한 삽입정렬 코드는 다음과 같습니다.

// 삽입 정렬: N^2 순회
int key, j;
for (int i = 1; i < N; i ++) {
    key = arr[i];
    for (j = i-1 ; j >= 0 ; j --) {
        if (arr[j] > key) arr[j+1] = arr[j];
        else break;
    }

    arr[j + 1] = key;

    System.out.println(Arrays.toString(arr));
}