알고리즘 및 개념 정리

이진 삽입 정렬 (Binary Insertion Sort) 에 관하여...

킹갓왕동현 2024. 5. 31. 02:33

오늘은 원래 팀 정렬을 다루려고 했었으나,

짧은 준비기간 안에 포스팅하기 너무 빡세기도 하고,

팀 정렬 자체가

이진 삽입 정렬 + 합병 정렬

두 가지의 조합이기 때문에,

 

기존에 다뤘던 삽입 정렬에

이분탐색 절차를 추가해서

삽입될 key 값의 위치를 보다 빠르게 찾는

이진 삽입 정렬을 먼저 다뤄보려고 합니다.

 

기존의 삽입 정렬은 매 회전마다 키 값을 정해서,

해당 키 값의 앞선 인덱스 값들과 대소를 비교한 뒤

알맞는 위치에 삽입하는 방식이었습니다.

 

이진 삽입 정렬도 큰 틀에서는 마찬가지입니다만,

 

기존 삽입 정렬에서는

배열이 길면 뒤쪽에 위치해있는 키 값일수록

한참 앞에 삽입돼야 하는 경우에도

모든 앞선 인덱스와 대소를 비교하면서

삽입될 위치를 찾아야 했습니다.

 

헌데 삽입정렬은 매 회전마다

키 값의 앞선 인덱스들이 모두 정렬된 상태가 되기 때문에,

 

정렬된 상태의 배열에서 키 값의 위치를 찾는

이분 탐색( = 이진 탐색) 알고리즘을 적용할 수 있습니다.

 

그래서,

기존 삽입정렬에서 매 회전시

키 값이 자리할 위치를 이진 탐색 알고리즘을 통해 찾는 것을

이진 삽입 정렬이라고 합니다.

 

설명으론 이해가 안될 수 있으니, 코드로써 비교해보겠습니다.

 

먼저 기존 삽입정렬 코드입니다.

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        //삽입 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        int key; // 조건이 맞으면 삽입할 변수 생성
        // 변수명이 key 인 이유는,
        // 삽입정렬에서 key 값은 고정된 채로,
        // 자신보다 앞선 인덱스들과 차례대로 비교를 하기 때문입니다.
        for (int i = 1; i < arr.length; i++) {
            key = arr[i]; // 현재 인덱스의 값을 key 로 할당.
            int j = i - 1; // 맨 처음 비교를 시작할 key 값의 바로 앞 인덱스.
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
                // key 값의 바로 앞 인덱스부터 비교해서,
                // 비교를 통해 삽입될 위치를 찾아갑니다.
            }
            arr[j + 1] = key;
            // while 문이 종료되면 위치를 찾은 것이기 때문에,
            // 맞는 위치에 key 값을 삽입합니다.
        }
        System.out.println(Arrays.toString(arr));
    }
}

 

 

이제 key 값이 들어갈 위치를 찾는 과정인

binarySearch 메소드를 삽입해야 하는데,

 

이진 탐색 알고리즘을 먼저 간단히 설명하자면,

이미 정렬된 배열에서만 탐색이 가능한데,

 

                                                                                

1 부터 100 중에 특정 숫자를 고르고,

up & down 을 통해 힌트를 줄게 맞혀봐. 라고 하면,

가장 일관되게 효율적인 접근 방식은

수의 범위를 절반씩 줄여나가는 것이고,

이것이 이분 탐색 알고리즘입니다.

                                                                                

 

찾고자 하는 target number 를 설정하고,

해당 배열에서 범위를 반씩 줄여가며 찾아야 하니,

low 값과 high 값을 가지고 반을 나눠서 middle 값을 받은 뒤에,

타겟을 middle 값과 대소를 비교해서,

타겟이 작으면 high 값을 줄여야 할 것이고,

타겟이 크면 low 값이 커져야 할 것입니다.

 

이 과정을 반복하는데,

반복문이 실행되는 조건을 low 값이 high 값보다 작은 동안으로 놓으면,

low 값과 high 값이 늘어나거나 줄어들면서

결국 타겟의 가장 작은 범위를 찾게됩니다.

 

그럼 이제 이진 탐색 알고리즘을 활용해서

완성된 이진 삽입 정렬을 코드로 보여드리겠습니다.

import java.util.Arrays;

public class BinaryInsertionSort {
    public static void main(String[] args) {
        //이진 삽입 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.

        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];

            int index = binarySearch(arr, key, 0, i);
            // binarySearch 메소드를 통해서
            // key 값이 삽입될 위치를 찾습니다.
            int j = i - 1;
            // 원래는 key 값과 비교를 하기 위한 j 값이었지만,
            // 여기서는 단순 시프트를 하기 위한 것입니다.
            while (j >= index) {
                arr[j + 1] = arr[j];
                j--;
                // index 위치엔 key 값이 들어갈 것이고,
                // 그 전까지의 값들을 반복해서 시프트 합니다.
            }
            arr[index] = key;
            // 이진 탐색을 통해 찾은 위치에 key 값이 들어가고,
            // 반복문을 통해 배열이 정렬됩니다.
        }
        System.out.println(Arrays.toString(arr));
    }

    static int binarySearch(int[] arr, int target, int low, int high) {
        // 원본 배열 arr, 타겟 넘버 target,
        // 정렬된 배열의 범위를 low 와 high 라는 인자로 받았습니다.
        while (low < high) {
            int middle = (low + high) / 2;
            // 좀 더 빠른 연산을 위해 / 2 부분을
            // 시프트 연산자를 써서 >>> 1 로 바꿔도 됩니다.
            // 또, 만약 정렬할 배열이 int 범위를 넘어가는 큰 배열이면
            // low + (high - low) / 2; 로 식을 바꿔야 합니다.
            if (arr[middle] > target) high = middle;
            else low = middle + 1;
            // 대소를 비교해서 high 와 low 범위를 좁혀줍니다.
        }

        return low;
        // 어차피 low 와 high 가 같아져야 반복문이 종료되기 때문에,
        // low 나 high 아무것이나 리턴돼도 상관없습니다.
    }
}

 

시간이 없어서

이진 탐색 알고리즘 부분을 따로 빼서 설명하지 않고

바로 이진 탐색 정렬로 한번에 구현한 관계로,

글만 보고 이해가 쉽게 되지 않을 수 있다고 생각합니다.

이 점 죄송하게 생각하고,

궁금하신 부분은 댓글이나 연락 주시면 성실히 답변드리겠습니다!

 

읽어주셔서 감사합니다.