[알고리즘] 정렬(Sorting) - Insertion(삽입) & Binary Insertion(이진 삽입) [개념과 구현]

Kyung Jae, Cheong·2024년 10월 23일

Java python 알고리즘

알고리즘-Algorithms

목록 보기

4/15

본 시리즈는 프로그래밍 알고리즘의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
- IDE : IntelliJ IDEA (Ultimate Edition)
- Java : JDK 21 (corretto-21)
- Python : 3.9 (conda env)

[알고리즘] 정렬(Sorting) - Insertion Sort & Binary Insertion Sort

정렬 알고리즘의 전반적인 개요와 분류는 다음 포스팅에서 확인하실 수 있습니다.
- [알고리즘] 정렬(Sorting) - 개요 (Java와 Python의 주요 정렬 방식 소개)

1. 단순 정렬 (Basic Sorting)

단순 정렬(Basic Sorting) 알고리즘은 기본적인 정렬 방식으로, 구현이 간단하고 상대적으로 이해하기 쉽습니다.

주로 데이터 크기가 작거나, 이미 정렬된 데이터에 대해 사용될 수 있습니다.
그러나 대부분의 경우 시간 복잡도가 $O(n^2)$ 로 비효율적이기 때문에, 대규모 데이터에서는 잘 사용되지 않습니다.

단순 정렬 알고리즘은 비교 기반 정렬로, 배열이나 리스트의 요소를 차례로 비교하며 정렬을 수행합니다.

각 알고리즘은 비교적 간단한 동작 원리를 기반으로 하기 때문에, 이해하기 쉽고 초보자에게 적합합니다.

대표적인 단순 정렬 알고리즘으로는 버블 정렬 (Bubble Sort), 선택 정렬 (Selection Sort), 삽입 정렬 (Insertion Sort) 등이 있으며, 이들은 주로 교육용이나 작은 데이터셋에 적합합니다.

실무 관점에서는 이 중에서 가장 중요하다 여겨지는 알고리즘은 삽입 정렬 (Insertion Sort)이라 볼수 있습니다.

다양한 프로그래밍 언어에서 일반적으로 작은 길이의 데이터에 대한 표준 정렬 알고리즘으로 가장 많이 쓰이는 방식이기 때문입니다.

저번 포스팅에서는 버블 정렬과 선택 정렬을 다루었고, 이번 포스팅에서 삽입 정렬과 이진 삽입 정렬을 다룰 예정입니다.

2. Insertion Sort (삽입 정렬)

2.1 Insertion Sort란?

삽입 정렬 (Insertion Sort)은 배열을 두 부분으로 나누어, 정렬된 부분과 정렬되지 않은 부분을 점차 확장해나가며 정렬하는 방식입니다.

배열의 각 요소를 하나씩 정렬된 부분에 삽입하여 최종적으로 전체 배열을 정렬합니다.
이 알고리즘은 이미 정렬된 배열에서 매우 효율적이며, 작은 데이터셋에서는 비교적 빠르게 작동합니다.
- 그렇기 때문에 실무에서도 작은 데이터의 정렬에 자주 사용되며, 특히 Java에서는 작은 길이의 기본형 배열을 정렬할 때 삽입 정렬이 주로 사용됩니다.

시간 복잡도:

최악 $O(n^2)$
최선 $O(n)$ (이미 정렬된 경우)

특징:

안정 정렬 (중복 데이터의 순서가 유지됩니다)
배열이 거의 정렬된 상태에서 효율적입니다.

2.2 Insertion Sort 동작 원리

Insertion Sort는 다음과 같은 순서로 동작합니다:

배열의 두 번째 요소부터 정렬되지 않은 부분을 시작으로 선택합니다.
선택한 요소를 앞쪽의 정렬된 부분과 비교하여, 알맞은 위치에 삽입합니다.
이 과정을 배열의 끝까지 반복하여 정렬된 부분을 확장합니다.

동작 예시:
주어진 배열 [9, 2, 1, 5, 4]을 삽입 정렬로 정렬하는 과정:

첫 번째 패스: 2를 첫 번째 자리 9와 비교하여 교환
- [9, 2, 1, 5, 4] → [2, 9, 1, 5, 4]
두 번째 패스: 1을 앞의 두 요소 2와 9와 비교하여 첫 번째 자리에 삽입
- [2, 9, 1, 5, 4] → [1, 2, 9, 5, 4]
세 번째 패스: 5를 앞의 요소들과 비교하여 네 번째 자리에 삽입
- [1, 2, 9, 5, 4] → [1, 2, 5, 9, 4]
네 번째 패스: 4를 앞의 요소들과 비교하여 네 번째 자리에 삽입
- [1, 2, 5, 9, 4] → [1, 2, 4, 5, 9] (정렬 완료)

2.3 Insertion Sort 구현 (Java)

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 앞의 정렬된 부분에서 key가 들어갈 위치를 찾음
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // 한 칸씩 오른쪽으로 이동
                j = j - 1;
            }
            arr[j + 1] = key; // key를 올바른 위치에 삽입
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 2, 1, 5, 4};
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Java 구현 설명:

배열의 두 번째 요소부터 시작하여, 정렬되지 않은 부분의 요소를 앞쪽의 정렬된 부분에 적절히 삽입합니다.
이중 반복문을 사용하여 배열을 순차적으로 정렬하며, 비교 및 교환이 이루어집니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

2.4 Insertion Sort 구현 (Python)

def insertion_sort(arr):
    # 배열의 두 번째 요소부터 시작
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # key가 들어갈 위치를 찾으며, 정렬된 부분에서 비교
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 요소들을 한 칸씩 오른쪽으로 이동
            j -= 1
        arr[j + 1] = key  # key를 올바른 위치에 삽입

# 예시 배열
arr = [9, 2, 1, 5, 4]
insertion_sort(arr)
print("Sorted array:", arr)

Python 구현 설명:

for문을 사용하여 배열의 두 번째 요소부터 시작하여, 정렬되지 않은 부분을 순차적으로 처리합니다.
while문을 통해 key가 들어갈 적절한 위치를 찾고, 나머지 요소를 오른쪽으로 이동시켜 자리를 만듭니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

3. Binary Insertion Sort (이진 삽입 정렬)

이진 삽입 정렬 (Binary Insertion Sort)은 삽입 정렬의 변형으로, 요소를 삽입할 위치를 찾기 위해 이진 탐색을 사용하여 비교 횟수를 줄이는 방식입니다.

3.1 Binary Insertion Sort란?

Binary Insertion Sort는 이진 탐색을 활용하여 삽입할 위치를 찾는 삽입 정렬의 변형 알고리즘입니다.

기존의 삽입 정렬은 비교를 선형적으로 진행하지만, Binary Insertion Sort는 이진 탐색을 사용하여 삽입할 위치를 빠르게 찾을 수 있어 비교 횟수를 줄일 수 있습니다.
- 그러나 삽입 후 데이터의 이동 비용은 여전히 존재하기 때문에, 전체적인 시간 복잡도는 여전히 $O(n^2)$ 입니다.
이 알고리즘은 정렬된 부분이 커질수록 더욱 효율적으로 동작합니다.
특히 Java와 Python의 TimSort 알고리즘에서 작은 구간의 정렬에 이진 삽입 정렬이 자주 사용됩니다.

시간 복잡도:

최악 $O(n^2)$ (비교 비용은 줄어들지만, 삽입 후 데이터 이동 비용은 동일)
최선 $O(n \log n)$ (이미 정렬된 경우)

특징:

이진 탐색을 사용해 비교 횟수를 줄임
데이터 이동은 여전히 발생하지만, 비교 비용이 줄어듬

3.2 Binary Insertion Sort 동작 원리

Binary Insertion Sort는 다음과 같은 순서로 동작합니다:

배열의 두 번째 요소부터 시작하여, 삽입할 위치를 이진 탐색으로 찾습니다.
이진 탐색을 사용해 삽입 위치를 찾은 후, 그 자리에 요소를 삽입하기 위해 필요한 만큼 요소들을 오른쪽으로 이동시킵니다.
이 과정을 배열의 끝까지 반복하여 배열을 정렬합니다.

동작 예시:
주어진 배열 [9, 2, 1, 5, 4]을 이진 삽입 정렬로 정렬하는 과정:

첫 번째 패스: 2를 이진 탐색으로 삽입할 위치를 찾아 교환
- [9, 2, 1, 5, 4] → [2, 9, 1, 5, 4]
두 번째 패스: 1을 이진 탐색으로 찾아 앞의 두 요소 사이에 삽입
- [2, 9, 1, 5, 4] → [1, 2, 9, 5, 4]
세 번째 패스: 5를 이진 탐색으로 적절한 위치에 삽입
- [1, 2, 9, 5, 4] → [1, 2, 5, 9, 4]
네 번째 패스: 4를 이진 탐색으로 찾아 알맞은 자리에 삽입
- [1, 2, 5, 9, 4] → [1, 2, 4, 5, 9] (정렬 완료)

3.3 Binary Insertion Sort 구현 (Java)

import java.util.Arrays;

public class BinaryInsertionSort {
    public static void binaryInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int left = 0;
            int right = i - 1;

            // 이진 탐색으로 삽입 위치 찾기
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] > key) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 삽입 위치까지 배열 요소 이동
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }

            // key를 찾은 위치에 삽입
            arr[left] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 2, 1, 5, 4};
        binaryInsertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Java 구현 설명:

이진 탐색을 통해 삽입할 위치를 찾고, 그 자리에 데이터를 삽입하기 위해 배열의 다른 요소들을 이동시킵니다.
삽입 위치를 빠르게 찾는 점에서 삽입 정렬보다 효율적입니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

3.4 Binary Insertion Sort 구현 (Python)

def binary_insertion_sort(arr):
    # 배열의 두 번째 요소부터 시작
    for i in range(1, len(arr)):
        key = arr[i]
        left = 0
        right = i - 1
        
        # 이진 탐색으로 삽입 위치 찾기
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1
        
        # 삽입 위치까지 배열 요소 이동
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]
        
        # key를 찾은 위치에 삽입
        arr[left] = key

# 예시 배열
arr = [9, 2, 1, 5, 4]
binary_insertion_sort(arr)
print("Sorted array:", arr)

Python 구현 설명:

이진 탐색을 사용해 삽입 위치를 찾아 배열의 요소를 오른쪽으로 이동시키고, 그 위치에 key를 삽입합니다.
Python에서도 이진 삽입 정렬은 TimSort 알고리즘의 일부로 자주 사용됩니다.

출력 예시:

Sorted array: [1, 2, 4, 5, 9]

4. 단순 정렬 알고리즘 비교

단순 정렬 알고리즘들은 구현이 쉽고 이해하기 간단하지만, 대규모 데이터에서는 비효율적일 수 있습니다.

특히, 삽입 정렬은 작은 데이터셋에서 자주 사용되며, 이미 정렬된 배열에서 가장 효율적으로 동작합니다.

알고리즘	시간 복잡도 (최악, 평균)	공간 복잡도	특징
Bubble Sort	$O(n^2)$	$O(1)$	구현이 간단하지만 비교 및 교환이 빈번하게 발생
Selection Sort	$O(n^2)$	$O(1)$	교환 횟수는 적지만, 비교 횟수는 많음
Insertion Sort	$O(n^2)$ (최선 $O(n)$ )	$O(1)$	작은 배열이나 이미 정렬된 배열에서 효율적
Binary Insertion	$O(n^2)$ (최선 $O(n \log n)$ )	$O(1)$	이진 탐색을 통해 비교 횟수를 줄이지만, 데이터 이동 비용은 그대로

삽입 정렬은 요소를 순차적으로 정렬된 부분에 삽입해나가는 방식으로, 작은 배열이나 이미 어느 정도 정렬된 배열에서 매우 효율적입니다.
이진 삽입 정렬은 이진 탐색을 통해 삽입할 위치를 빠르게 찾지만, 데이터 이동 비용이 존재하기 때문에 시간 복잡도는 여전히 $O(n^2)$ 입니다.

이들 알고리즘은 모두 작은 배열에서의 사용에 적합하며, 대규모 데이터에서는 보다 효율적인 정렬 알고리즘을 사용하는 것이 바람직합니다.

마무리

이번 포스팅에서는 삽입 정렬과 이진 삽입 정렬의 개념, 동작 원리, 그리고 Java와 Python에서의 구현을 살펴보았습니다.

삽입 정렬은 작은 데이터셋이나 이미 어느 정도 정렬된 배열에서 매우 효율적으로 작동하며, 안정성을 갖춘 대표적인 정렬 알고리즘입니다.
이진 삽입 정렬은 이진 탐색을 사용하여 비교 횟수를 줄일 수 있지만, 데이터 이동 비용은 여전히 발생하므로 전체적인 시간 복잡도는 $O(n^2)$ 에서 벗어나지 못합니다.

이러한 단순 정렬 알고리즘들은 간단한 구조와 직관적인 동작 원리로 인해 학습 목적으로도 많이 사용되며, 작은 크기의 배열에서는 실용적인 선택이 될 수 있습니다. 하지만 대규모 데이터를 처리할 때는 다른 효율적인 정렬 알고리즘을 사용하는 것이 바람직합니다.

다음 포스팅에서는 힙 정렬 (Heap Sort), 트리 정렬 (Tree Sort), 등 트리 데이터 구조를 활용하여 데이터를 정렬하는 방식들을 다루도록 하겠습니다.