yg log --graph --oneline --all

Home Stack Notes AboutRSS

1. 삽입 정렬은 이미 정렬된 구간을 믿는다

작성 · 5분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

들어가며

정렬은 여러 값을 정해진 순서로 다시 배치하는 작업이다. 이 글에서는 정수 배열을 작은 값부터 큰 값 순서로 만드는 오름차순 정렬을 다룬다. 배열의 위치 번호인 인덱스는 0부터 세며, arr[i]는 번호가 i인 칸의 값이다. 비교는 두 값의 순서를 알아내며, 교환은 두 칸의 값을 맞바꾼다.

예를 들어 [4, 2, 3]을 정렬하면 [2, 3, 4]가 된다. 중요한 것은 결과만이 아니라 매 단계에서 배열의 어느 구간이 이미 정렬됐고 어느 구간이 아직 남았는지 구분하는 일이다.

삽입 정렬을 구현한 코드에는 이런 주석이 남아 있다.

이해가 잘 안가는데??

코드는 짧았다. 정렬할 값을 key에 보관하고, 왼쪽 원소가 key보다 크면 한 칸씩 오른쪽으로 옮긴다. 그런데 반복문이 중간에서 끝나는 것이 선뜻 납득되지 않았다. 노트에는 당시의 의문이 조금 더 길게 남아 있다.

그 뒤에도 검사해봐야 하는거 아니에요??

내가 놓치고 있던 것은 j 뒤에 원소가 더 있느냐가 아니었다. 지금 보고 있는 왼쪽 구간이 이미 정렬되어 있다는 사실이었다. 삽입 정렬의 핵심은 새 원소를 매번 처음부터 정렬하는 것이 아니라, 이미 정렬된 구간에 원소 하나를 끼워 넣는 데 있다.

끝까지 비교하는 선택 정렬

선택 정렬은 아직 정렬되지 않은 구간을 끝까지 살핀다. 오름차순으로 정렬한다면 현재 위치 i부터 마지막 위치까지 최솟값을 찾은 뒤 arr[i]와 바꾼다.

핵심 반복문을 읽기 쉽게 함수 이름을 정리해 옮기면 다음과 같다.

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_i = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_i]) min_i = j;
        }
        swap(&arr[i], &arr[min_i]);
    }
}

한 번의 바깥 반복이 끝나면 arr[i]의 자리는 확정된다. 하지만 최솟값을 찾으려면 남은 구간을 모두 봐야 한다. 중간에 지금까지 가장 작은 수를 찾았다고 생각해도, 아직 보지 않은 뒤쪽에 더 작은 수가 있을 수 있기 때문이다.

이 방식과 나란히 놓으면 노트의 의문이 더 분명해진다. 선택 정렬에서는 뒤쪽을 모두 확인해야 하는데, 삽입 정렬은 어떤 근거로 비교를 중간에 멈춰도 되는 걸까?

삽입 정렬에서 멈춰도 되는 이유

삽입 정렬도 저장소 코드의 함수 이름과 변수명을 위 예시에 맞춰 옮겨 보자.

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

여기서 바깥 반복이 시작될 때마다 arr[0..i-1]은 이미 오름차순으로 정렬되어 있다. 이 조건이 매 반복에서 유지되는 불변식이다.

작은 배열 [2, 4, 7, 5]에서 5를 삽입해 보자. key는 5이고 j는 2에서 시작한다.

  1. arr[2]는 7이다. 7은 5보다 크므로 오른쪽으로 옮긴다. 배열은 잠시 [2, 4, 7, 7]이 된다.
  2. arr[1]은 4이다. 4는 5보다 크지 않으므로 반복을 멈춘다.
  3. 5가 들어갈 자리인 arr[2]에 key를 넣어 [2, 4, 5, 7]을 만든다.

이때 4의 왼쪽에 있는 2를 다시 볼 필요가 없다. 왼쪽 구간이 이미 정렬되어 있으므로 2는 4보다 작거나 같고, 따라서 5보다도 작다. 현재 원소 하나와의 비교가 그보다 왼쪽에 있는 원소들의 관계까지 알려준다.

반대로 key가 왼쪽의 모든 원소보다 작으면 j가 -1이 될 때까지 밀어낸다. 이때는 j >= 0 조건 때문에 멈추고, 마지막 대입의 j + 1은 0이 된다. 비교할 원소를 만난 경우와 배열의 왼쪽 끝을 지난 경우가 같은 대입으로 이어진다.

당시 노트에는 “arr[j]가 key보다 크면 정렬을 멈춘다”는 취지의 문장도 적혀 있었다. 하지만 실제 코드는 반대다. arr[j] > key인 동안은 이동을 계속하고, arr[j] <= key가 되는 순간 멈춘다. 내가 얻은 핵심 이해는 맞았지만, 이를 설명하는 비교 방향은 뒤집혀 있었다. 코드와 작은 입력을 함께 따라가야 했던 이유다.

같은 이차 시간 안에서 생기는 차이

선택 정렬과 삽입 정렬의 최악 시간 복잡도는 둘 다 O(n²)이다. 그렇다고 두 알고리즘이 같은 일을 하는 것은 아니다.

선택 정렬은 입력이 이미 정렬되어 있어도 남은 구간의 최솟값을 찾기 위해 거의 같은 횟수로 비교한다. 대신 한 바깥 반복에서 교환은 많아야 한 번이다. 삽입 정렬은 key보다 큰 원소들을 직접 밀어야 하므로 역순 배열에서는 이동이 많다. 반대로 이미 정렬된 배열에서는 첫 비교에서 바로 멈출 수 있다.

그래서 예전 노트에 적었던 “정렬되지 않은 배열에서는 선택 정렬이 더 빠르다”는 문장을 조건 없는 결론으로 가져오기는 어렵다. 입력에 역전된 원소 쌍이 얼마나 많은지, 비교와 메모리 이동 중 무엇이 더 비싼지, 컴파일러와 측정 환경이 어떤지에 따라 실제 시간은 달라진다. Big-O는 입력 크기에 따른 성장률을 설명하지만, 같은 성장률 안의 작업 구성까지 같다고 말하지 않는다.

이번 글에서는 구체적인 실행시간 숫자를 싣지 않았다. 당시 저장소에는 clock()으로 같은 난수 배열을 비교하는 코드가 있지만, 한 번의 난수 입력과 한 번의 측정만으로 일반적인 성능 순서를 정할 수 없기 때문이다. 숫자를 비교하려면 정렬·역정렬·무작위·중복 입력을 나누고, 동일한 조건에서 반복 측정해야 한다.

지금 남아 있는 이해

삽입 정렬을 이해하게 만든 것은 반복문의 문법이 아니라 반복문에 들어올 때 이미 참인 조건이었다. arr[0..i-1]이 정렬되어 있기 때문에, key보다 작거나 같은 원소를 만난 순간 그보다 왼쪽은 더 볼 필요가 없다.

선택 정렬은 아직 모르는 구간 전체에서 답을 찾고, 삽입 정렬은 이미 알고 있는 순서를 이용해 탐색을 일찍 끝낸다. 둘 다 단순한 O(n²) 정렬이지만, 어느 비교를 생략할 수 있는지를 묻기 시작하면 전혀 다른 알고리즘으로 보인다.

참고한 기록과 코드

관련 포스트