정렬 - 삽입 정렬 (Insertion Sort)

#1 알고리즘

#1-1

 

#1-2

 

#2 코드

#2-1 자바

public static void insertionSort(int[] array, int startIndex, int endIndex) {
    for(int maxIndex = (startIndex + 1); maxIndex <= endIndex; maxIndex++) {
        // array[maxIndex]가 최댓값인 경우
        if(array[maxIndex - 1] <= array[maxIndex]) {
            continue;
        
        // array[maxIndex]가 최댓값이 아닌 경우
        } else {
            insertion(array, startIndex, maxIndex);
        }
        
        
    }
}

private static void insertion(int[] array, int startIndex, int insertIndex) {
    
    // 삽입 위치 찾기
    int insertionDestination = -1;
    for(int i = startIndex; i < insertIndex; i++) {
        
        /*
            * if(array[i] <= array[insertIndex]) { insertionDestination = i + 1 } 라고 쓰면 안 된다.
            * 왜냐하면,
            * array[insertIndex]가 array의 최솟값인 경우, 삽입 위치를 찾을 수 없기 때문이다. (insertionDestination의 값이 -1에서 변경되지 않음)
            * 그렇다면,
            * if(array[insertIndex] <= array[i]) { insertionDestination = i } 라고 쓰는 것은 '왜' 되는가?
            * array[insertIndex]는 '반드시 최댓값이 아니다' (insertSort() 참조)
            * 따라서, 이 경우 insertionDestination의 값엔 반드시 -1을 초과한 값(배열의 인덱스)이 할당된다.
            */
        if(array[insertIndex] <= array[i]) {
            insertionDestination = i;
            break;
        }
    }
    
    // 삽입 위치에 따른 array의 인덱스 조정
    int temp = array[insertIndex];
    for(int i = (insertIndex - 1); i >= insertionDestination; i--) {
        array[i + 1] = array[i];
    }
    array[insertionDestination] = temp;
}

 

#2-2 코틀린

fun insertionSort(array: Array<Int>, startIndex : Int, endIndex : Int) {

    for(maxIndex : Int in (startIndex + 1)..endIndex) {
        // array[maxIndex]가 최댓값인 경우
        if(array[maxIndex - 1] <= array[maxIndex]) {
            continue

        // array[maxIndex]가 최댓값이 아닌 경우
        } else {
            insertion(array, startIndex, maxIndex)
        }
    }
}

fun insertion(array: Array<Int>, startIndex : Int, insertIndex: Int) {

    // 삽입 위치 찾기
    var insertionDestination = -1
    for(i : Int in startIndex..<insertIndex) {

        /*
         * if(array[i] <= array[insertIndex]) { insertionDestination = i + 1 } 라고 쓰면 안 된다.
         * 왜냐하면,
         * array[insertIndex]가 array의 최솟값인 경우, 삽입 위치를 찾을 수 없기 때문이다. (insertionDestination의 값이 -1에서 변경되지 않음)
         * 그렇다면,
         * if(array[insertIndex] <= array[i]) { insertionDestination = i } 라고 쓰는 것은 '왜' 되는가?
         * array[insertIndex]는 '반드시 최댓값이 아니다' (insertSort() 참조)
         * 따라서, 이 경우 insertionDestination의 값엔 반드시 -1을 초과한 값(배열의 인덱스)이 할당된다.
         */
        if(array[insertIndex] <= array[i]) {
            insertionDestination = i
            break
        }
    }

    // 삽입 위치에 따른 array의 인덱스 조정
    val temp = array[insertIndex]
    for(i : Int in (insertIndex - 1) downTo insertionDestination) {
        array[i + 1] = array[i]
    }
    array[insertionDestination] = temp
}

 

#3 요약

삽입 정렬은 정렬된 배열에 값을 '삽입'하고, 그 뒤의 원소들을 밀어내는 정렬이다.

 

#4 이 개념이 사용된 글

[백준] 27522 - 카트라이더: 드리프트