삽입 정렬

삽입 정렬

삽입 정렬은 2번째 인덱스부터 시작해서 해당 인덱스 앞의 모든 수들과 비교해 해당 인덱스의 수보다 크면 앞으로 삽입하며 정렬하는 방법입니다.

우선 key값은 배열 인덱스 1번부터 시작입니다. i 이전의 원소를 비교해야 하는데, 인덱스가 0이면 비교할게 없습니다. key는 8로 8보다 큰 값은 오른쪽으로 밀어버립니다. 8보다 작은 원소가 발견되면 그 원소 뒤에 8을 삽입해야하는 데, 없으므로 제일 앞에 삽입합니다.

8이 맨앞에 삽입 되고 난 후 i가 하나 증가하여 계속 비교합니다. key는 1이 됩니다. 1보다 작은 원소가 없으므로 제일 앞에 위치하게 됩니다.

이후 i가 하나 증가하고 키는 3입니다. 3보다 작은 원소를 만날때 그 뒤에 삽입하는 과정을 아래 그림이 보여줍니다.

이제 i가 하나 증가하게 되고 마지막 원소인 2가 키가 됩니다. 2보다 작은 원소는 1이므로 1뒤에 2를 삽입하는 것이 됩니다. 아래 그림이 그 과정을 보여줍니다.

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

시간복잡도

이중 반복문 → $O(N^2)$

구현

class Solution {
    public int[] insertionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j-1]) {
                    int tmp = nums[j-1];
                    nums[j-1] = nums[j];
                    nums[j] = tmp;
                // 이미 if문 수들 앞은 정렬이 되어 있다    
                } else {
                    break;
                }
            }
        }
        return nums;
    }
}