삽입 정렬(Insertion sort)

삽입 정렬(Insertion sort)

삽입 정렬은 원소가 있어야 하는 자리에 '삽입'한다고 하여 삽입 정렬이다.

5, 7, 2, 4 ,6 이라는 원소가 있고, 여기서 세 번째 원소인 2를 선택했다고 하자. 오름차순 정렬이라면 2는 맨 첫 번째에 위치해야 한다. 방법은 간단하다. 2보다 앞에 위치한 원소를 하나씩 비교하며 앞의 원소보다 2가 더 작다면 한 칸씩 앞으로 보내면 된다. 앞에서 공부한 버블, 선택 정렬과 마찬가지로 두 번째 원소부터 비교를 시작한다. 이전 원소들을 비교해나가기 때문에 첫 번째 원소부터 시작하지 않아도 된다.

버블 정렬, 선택 정렬과 같이 제자리 정렬(in-place) 알고리즘이다. 또한 버블, 선택 정렬에 비해 속도가 빠르다. 배열이 길어질수록 효율이 떨어진다는 단점이 있다.

삽입 정렬 알고리즘의 진행 과정이다. 두 번째 원소부터 시작하여 각 원소의 알맞은 위치를 찾아서 '삽입'한다.

Java로 삽입 정렬 구현

private static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        //i번째 요소를 임의의 변수에 저장한다.
        int temp = arr[i];
        //비교할 요소를 가진 인덱스(삽입할 요소의 이전 원소)
        int prev = i - 1;

        /*
        * prev가 0보다 크거나 같고 &&
        *    arr[prev] 즉, 이전 인덱스가 가진 요소가 temp(현재 삽입할 위치를 찾으려고 하는 인덱스의 요소)보다 크다면
        *    조건식을 달성한다.
        *    만약 이전 요소보다 현재 삽입하려는 요소가 더 큰 값이라면 while문에 들어가지 못한다.
        **/
        while ( (prev >= 0) && (arr[prev] > temp)) {
            //현재 삽입할 위치를 찾고 있는 인덱스의 요소와 이전 요소의 자리를 바꾼다.
            arr[prev+1] = arr[prev];
            //그리고 prev를 1을 감소시킨다.
            prev--;
            //prev가 0 즉, 더 이상 비교할 인덱스가 없을 때까지 반복한다.
        }

        prev+1번째 인덱스가 temp(삽입할 요소)를 삽입해야 하는 위치다.
        arr[prev + 1] = temp;

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

위 코드는 위키피디아에서 가져온 것인데, 딱 코드만 읽어서는 당장 뭘 하는 코드인지 직관적이지 않은 것 같았다. 그래서 메소드로 역할을 나눠서 분배해봤다.

    private static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int prevIndex = i - 1;

            while (isValidIndex(prevIndex)
                    && isPreviousElementBigger(arr[prevIndex], temp)) {
                //이전 요소의 자리를 한 칸 뒤로 미룬다.
                prevElementSwapNextIndex(arr, prevIndex);
                //prevIndex를 감소시킨다.
                prevIndex--;
            }

            //요소를 제자리에 삽입한다.
            insertElement(arr, prevIndex, temp);

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

    //엘리먼트가 원래 위치해야 할 자리에 삽입한다.
    private static void insertElement(int[] arr, int index, int element) {
        arr[index + 1] = element;
    }

    //이전 요소가 현재 요소보다 클 때 이전 요소를 다음 인덱스로 이동시키는 메소드
    private static void prevElementSwapNextIndex(int[] arr, int prevIndex) {
        arr[prevIndex + 1] = arr[prevIndex];
    }

    //이전 요소가 더 크다면 true를 반환하는 메소드
    private static boolean isPreviousElementBigger(int prevElement, int targetElement) {
        //비교할 인덱스가 존재하고, 이전 요소가 더 크다면 true
        return prevElement > targetElement;
    }

    //index유효성 검사
    private static boolean isValidIndex(int prevIndex) {
        return prevIndex >= 0;
    }

기존 while문 조건식의 코드는 (prev >= 0) && (arr[prev] > temp)인데 딱 봐서는 무엇을 비교하는지 알 수 없었다. 그래서 이해하기 쉽도록 메소드로 이름을 줬다.isValidIndex(prevIndex) && isPreviousElementBigger(arr[prevIndex], temp)은 index가 유효한 지 체크하고, 이전 요소가 검사하는 요소(temp)보다 더 크다면 true를 반환하는 메소드다. 영어가 맞는지는 모르겠지만... 전보다는 확실히 무엇을 비교하는지 나타내고 있는 듯하다.

그 다음은 prevElementSwapNextIndex(arr, prevIndex)메소드다. 기존 코드는 arr[prev+1] = arr[prev]이었다. 역시 이 부분만 떼어놓고 봤을 때 어떤 코드인지 알 수 없다. prevElementSwapNextIndex()이라고 이 코드를 처음 보는 사람일지라도 대충 뭔가를 바꾸는 코드라는 것 정도는 알 수 있다.

마지막은 insertElement() 메소드다. 기존 코드는 arr[prev + 1] = temp였다. 역시 딱 봐서 뭘 하는 코드인지 알 수 없다. 이 코드의 목적이 요소가 있어야 할 자리에 삽입하는 것이므로 insertElement()이라고 이름을 줘서 요소를 삽입하는 메소드라는 것을 쉽게 알 수 있게 했다.
위키피디아에서 복사해서 가져온 코드를 메소드를 사용해 이름을 붙여주니 훨씬 이해하기 쉬운 코드가 되었다.