[Sort] 삽입 정렬 ( Insertion Sort)

소개

정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법이다.

 

동작원리

• 첫번째 자리는 정렬이 되었다고 가정한다.
• 두번째 자리를 target 으로 정하고 왼쪽의 정렬된 원소들과 target의 값을 비교한다.
• 만약 target 값보다 정렬된 왼쪽 원소들이 크다면 자리를 교환해준다.
• 다시 오른쪽으로 이동하여 target값을 저장하고 위의 순서대로 반복한다.

 

구현 코드

for (int i = 1; i < arr.length; i++) {
    int target = arr[i];
    int j;
    for (j = i - 1; j >= 0 && arr[j] > target; j--) {
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = target;
}