Insert Sort

• 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역으로 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬

public static void insertionSort(int[] numbers) {
        //1번 인덱스를 먼저 key로 삼고 시작
        for (int i = 1; i < numbers.length; i++) {
            int key = numbers[i];
            int j;

            //인덱스를 하나씩 줄이면서 비교. 키보다 큰거 발견시 삽입
            for (j = i - 1; j >= 0 && numbers[j] > key; j--) {
                numbers[j + 1] = numbers[j];
            }
            numbers[j + 1] = key;
        }
    }

• 최선의 경우 : O(n) - 이미 정렬
• 최악의 경우 O(n^2) - 역순
• 많은 이동이 필요하므로 레코드가 클 경우 불리
• 대부분 정렬되어 있으면 매우 효율적