정렬 알고리즘 정리

알고리즘 문제 풀이나 기술 면접에서 자주 등장하는 대표적인 정렬 알고리즘 8가지(거품, 선택, 삽입, 퀵, 병합, 힙, 기수, 계수 정렬)의 개념과 특징, 시간복잡도, 그리고 Java 코드를 정리해보았습니다.

1. 거품 정렬 (Bubble Sort)

서로 인접한 두 원소를 비교하여 정렬 기준에 맞지 않으면 자리를 교환하는 알고리즘입니다.

과정 (오름차순 기준)

1. 첫 번째 원소부터 인접한 원소와 비교하여 조건에 맞지 않으면 위치를 바꿉니다.
2. 1회전이 종료되면 가장 큰 원소가 배열의 맨 끝에 위치하게 됩니다.
3. 정렬되지 않은 나머지 원소들을 대상으로 위 과정을 반복합니다.

특징

• 구현이 간단하고 코드가 직관적입니다.
• 주어진 배열 안에서 교환하는 제자리 정렬(In-place Sort)입니다.
• 중복된 값의 순서가 바뀌지 않는 안정 정렬(Stable Sort)입니다.
• 교환 연산이 빈번하게 일어납니다.

시간복잡도

• 최악, 최선, 평균 모두 O(n^2)

코드

static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 각 회전마다 배열의 끝에서부터 하나씩 정렬되므로 탐색 범위를 줄임
        for (int j = 1; j < n - i; j++) {
            // 앞의 원소가 뒤의 원소보다 크면 교환 (오름차순 기준)
            if (arr[j - 1] > arr[j]) {
                int tmp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

2. 선택 정렬 (Selection Sort)

배열을 순회하며 최솟값(또는 최댓값)을 찾아 배열의 맨 앞 원소와 교환하는 알고리즘입니다.

과정 (오름차순 기준)

1. 주어진 배열을 순회하며 최솟값을 찾습니다.
2. 최솟값을 배열의 맨 앞 원소와 교환합니다.
3. 2회전부터는 정렬된 부분 다음의 배열부터 위 과정을 반복합니다.

특징

• 교환 횟수가 적어 시간 소요가 상대적으로 적습니다.
• 제자리 정렬입니다.
• 불안정 정렬(Unstable Sort)입니다.

시간복잡도

• 최악, 최선, 평균 모두 O(n^2)

코드

static void selectionSort(int[] arr) {
    int n = arr.length;
    // 마지막 원소는 자동으로 정렬되므로 n-1까지만 반복
    for (int i = 0; i < n - 1; i++) {
        int idx = i; // 현재 범위에서 최솟값의 인덱스를 저장할 변수
        
        // 정렬되지 않은 나머지 부분에서 최솟값 탐색
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[idx]) {
                idx = j;
            }
        }
        
        // 찾은 최솟값을 현재 위치(i)의 원소와 교환
        int tmp = arr[idx];
        arr[idx] = arr[i];
        arr[i] = tmp;
    }
}

3. 삽입 정렬 (Insertion Sort)

두 번째 원소부터 시작하여, 그 앞의 정렬된 배열과 비교해 자신이 들어갈 위치를 찾아 삽입하는 알고리즘입니다.

과정 (오름차순 기준)

1. 타겟 원소를 앞쪽 원소들과 역순으로 비교합니다.
2. 타겟보다 큰 원소들을 뒤로 한 칸씩 밀어내고 빈자리에 타겟을 삽입합니다.

특징

• 배열이 거의 정렬되어 있는 상태에서는 시간복잡도가 O(n)에 수렴할 정도로 빠릅니다.
• 제자리 정렬입니다.
• 안정 정렬입니다.

시간복잡도

• 최악, 평균: O(n^2)
• 최선: O(n)

코드

static void insertionSort(int[] arr) {
    int n = arr.length;
    // 두 번째 원소부터 타겟으로 삼아 탐색 시작
    for (int i = 1; i < n; i++) {
        int tmp = arr[i]; // 현재 삽입할 타겟 원소
        int prev = i - 1; // 타겟 원소와 비교할 이전 위치의 인덱스
        
        // 타겟보다 큰 원소들을 뒤로 한 칸씩 밀어냄
        while (prev >= 0 && arr[prev] > tmp) {
            arr[prev + 1] = arr[prev];
            prev--;
        }
        
        // 탐색을 마친 적절한 빈자리에 타겟 원소 삽입
        arr[prev + 1] = tmp;
    }
}

4. 퀵 정렬 (Quick Sort)

배열 안에서 한 요소를 피벗(Pivot)으로 선택하고, 피벗을 기준으로 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 분할한 뒤, 분할된 배열에 대해 이 과정을 반복하는 알고리즘입니다.

과정 (오름차순 기준)

1. 배열에서 피벗을 하나 고릅니다.
2. 피벗 앞에는 피벗보다 값이 작은 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 원소들이 오도록 배열을 분할합니다.
3. 분할된 두 배열에 대해 재귀적으로 분할 과정을 반복합니다. (배열의 크기가 1이 될 때까지)
4. 분할된 배열을 모두 합치면 정렬이 완료됩니다.

특징

• 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서 평균적으로 가장 빠릅니다.
• 제자리 정렬입니다.
• 불안정 정렬입니다.
• 피벗을 선택하는 방식에 따라 성능이 크게 달라질 수 있습니다.
• 분할 정복(Divide and Conquer) 알고리즘을 기반으로 합니다.

시간복잡도

• 평균, 최선: O(nlogn)
• 최악: O(n^2)

코드

static void quickSort(int[] arr, int l, int r) {
    // 배열의 크기가 1 이하이면 정렬 종료
    if (l >= r) {
        return;
    }

    // 배열 분할 후 피벗의 최종 위치를 얻어옴
    int pivot = partition(arr, l, r); 
    
    // 피벗을 기준으로 분할된 두 하위 배열을 재귀적으로 정렬
    quickSort(arr, l, pivot - 1);
    quickSort(arr, pivot + 1, r);
}

static int partition(int[] arr, int l, int r) {
    int pivot = arr[r]; // 가장 오른쪽 원소를 피벗으로 선택
    int i = l - 1; // 피벗보다 작은 원소들이 배치될 마지막 인덱스

    for (int j = l; j < r; j++) {
        // 현재 원소가 피벗보다 작거나 같으면 교환
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    // 피벗을 올바른 위치(작은 요소들과 큰 요소들 사이)로 이동
    int tmp = arr[i + 1];
    arr[i + 1] = arr[r];
    arr[r] = tmp;
    
    return i + 1; // 피벗이 위치하게 된 인덱스 반환
}

5. 병합 정렬 (Merge Sort)

하나의 배열을 두 개의 균등한 크기로 분할하고 부분 배열을 정렬한 다음, 두 부분 배열을 다시 합쳐서 전체가 정렬된 배열이 되게 하는 방식입니다.

과정 (오름차순 기준)

1. 배열을 같은 크기의 배열 2개로 나눕니다. (배열의 크기가 1이 될 때까지 반복)
2. 분할된 부분 배열들을 정렬합니다.
3. 정렬된 부분 배열들을 하나의 배열에 병합합니다.

특징

• 데이터의 분포에 영향을 받지 않고 항상 일정한 성능을 보장합니다.
• 제자리 정렬이 아닙니다. (별도의 임시 배열 필요)
• 안정 정렬입니다.
• 분할 정복 알고리즘을 기반으로 합니다.

시간복잡도

• 평균, 최선, 최악 모두 O(nlogn)

코드

static int[] ret; // 병합 결과를 임시로 담을 배열. 사전에 배열 크기에 맞게 초기화되어야 함

static void mergeSort(int[] arr, int l, int r) {
    // 배열의 크기가 1 이하이면 분할 종료
    if (l >= r) {
        return;
    }
    
    int m = (l + r) / 2; // 중간 지점 계산
    mergeSort(arr, l, m); // 왼쪽 부분 배열 정렬
    mergeSort(arr, m + 1, r); // 오른쪽 부분 배열 정렬
    merge(arr, l, m, r); // 정렬된 두 부분 배열을 하나로 병합
}

static void merge(int[] arr, int l, int m, int r) {
    int i = l; // 왼쪽 배열의 시작 인덱스
    int j = m + 1; // 오른쪽 배열의 시작 인덱스
    int k = l; // 임시 배열(ret)의 기록 시작 인덱스
    
    // 두 부분 배열의 원소를 비교하여 작은 값부터 임시 배열에 복사
    while(i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            ret[k++] = arr[i++];
        } else {
            ret[k++] = arr[j++];
        }
    }
    
    // 왼쪽 배열에 남은 원소가 있다면 모두 복사
    while (i <= m) {
        ret[k++] = arr[i++];
    }
    
    // 오른쪽 배열에 남은 원소가 있다면 모두 복사
    while (j <= r) {
        ret[k++] = arr[j++];
    }
    
    // 임시 배열에 정렬된 결과를 원본 배열에 반영
    for (int p = l; p <= r; p++) {
        arr[p] = ret[p];
    }
}

6. 힙 정렬 (Heap Sort)

완전이진트리를 기반으로 하는 힙(Heap) 자료구조를 이용한 정렬 알고리즘입니다.

과정 (오름차순 기준)

1. 주어진 배열의 원소들을 최대 힙(Max Heap) 구조로 구성합니다.
2. 최대 힙의 루트 노드(가장 큰 값)를 배열의 맨 마지막 원소와 교환합니다.
3. 힙의 크기를 1 줄이고 다시 힙 구조를 구성합니다.
4. 힙의 크기가 1이 될 때까지 이 과정을 반복합니다.

특징

• 시간복잡도가 같은 퀵 정렬이나 병합 정렬과 비교했을 때 캐시 지역성이 떨어져서 실제 수행 속도가 상대적으로 느린 편입니다.
• 제자리 정렬입니다.
• 불안정 정렬입니다.

시간복잡도

• 평균, 최선, 최악 모두 O(nlogn)

코드

static void heapSort(int[] arr) {
    int n = arr.length;

    // 1. 초기 배열을 최대 힙(Max Heap) 구조로 구성 (Bottom-up 방식)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 힙에서 요소를 하나씩 추출하여 배열의 끝으로 이동시키며 정렬
    for (int i = n - 1; i > 0; i--) {
        // 루트 노드(최댓값)를 현재 힙의 마지막 원소와 교환
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        // 힙의 크기를 줄이고(i), 루트 노드에 대해 다시 최대 힙 구조화
        heapify(arr, i, 0);
    }
}

static void heapify(int[] arr, int n, int i) {
    int largest = i; // 현재 부모 노드를 가장 큰 값으로 가정
    int l = 2 * i + 1; // 왼쪽 자식 노드 인덱스
    int r = 2 * i + 2; // 오른쪽 자식 노드 인덱스

    // 왼쪽 자식이 존재하고, 부모 노드보다 크면 largest 인덱스 갱신
    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    // 오른쪽 자식이 존재하고, 현재까지 가장 큰 노드보다 크면 largest 인덱스 갱신
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    // 부모 노드가 가장 큰 값이 아니라면 자식과 교환 후 재귀적으로 heapify 호출
    if (largest != i) {
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;

        heapify(arr, n, largest);
    }
}

7. 기수 정렬 (Radix Sort)

데이터의 각 자릿수를 기준으로 낮은 자릿수부터 높은 자릿수까지 차례대로 정렬을 수행하여 최종적으로 정렬된 결과를 얻는 알고리즘입니다.

과정 (오름차순 기준)

1. 주어진 배열에서 가장 큰 숫자를 찾아 최대 자릿수를 확인합니다.
2. 1의 자리를 기준으로 배열의 원소들을 정렬합니다. (내부적으로 계수 정렬 활용)
3. 이 과정을 가장 높은 자릿수까지 반복합니다.

특징

• 데이터를 직접 비교하지 않고 정렬하는 비비교 정렬입니다.
• 제자리 정렬이 아닙니다.
• 안정 정렬입니다.
• 문자열이나 정수처럼 자릿수가 있는 데이터에만 적용할 수 있어 한정적입니다.

시간복잡도

• 최상, 평균, 최악 모두 O(d * (N + K)) (d는 자릿수. 보통 N이 지배적이라 O(N)으로 간주)

코드

static void radixSort(int[] arr) {
    int max = 0;
    // 배열 내 최댓값을 탐색하여 최대 자릿수를 확인
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }

    // 1의 자리부터 시작하여 최대 자릿수까지 계수 정렬 수행
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] ret = new int[n]; // 정렬 결과를 임시로 저장할 배열
    int[] count = new int[10]; // 0~9까지 각 숫자의 발생 빈도를 저장할 배열

    // 현재 자릿수(exp)를 기준으로 발생 빈도 계산
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // 누적합을 계산하여 원소들이 배치될 인덱스 구간 확인
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 원본 배열을 역순으로 순회하며 위치 배정 (안정 정렬 유지를 위함)
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        ret[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 정렬된 임시 배열의 내용을 원본 배열에 복사
    for (int i = 0; i < n; i++) {
        arr[i] = ret[i];
    }
}

8. 계수 정렬 (Counting Sort)

데이터의 개수를 세서 정렬하는 알고리즘입니다.

과정 (오름차순 기준)

1. 배열을 순회하며 각 숫자가 몇 번 등장하는지 세어 count 배열에 저장합니다.
2. count 배열의 각 원소를 누적합 형태로 변환합니다.
3. 원본 배열의 끝에서부터 시작하여 숫자를 확인하고, count 배열에 기록된 위치에 해당 숫자를 배치합니다.
4. 모든 원소를 배치하면 정렬이 완료됩니다.

특징

• 데이터를 비교하지 않고 정렬하는 비비교 정렬입니다.
• 제자리 정렬이 아닙니다.
• 안정 정렬입니다.
• 데이터의 범위(최댓값)가 메모리 크기를 넘지 않을 때만 사용할 수 있으며, 중복된 값이 많고 데이터 범위가 좁은 경우 매우 효율적입니다.

시간복잡도

• 최선, 최악, 평균 모두 O(N + K) (보통 N이 지배적이라 O(N)으로 간주)

코드

static void countingSort(int[] arr) {
    int n = arr.length;

    // 카운트 배열의 크기를 결정하기 위해 최댓값 탐색
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        max = Math.max(max, arr[i]);
    }

    int[] count = new int[max + 1]; // 각 숫자의 발생 빈도를 저장할 배열
    int[] ret = new int[n]; // 정렬 결과를 저장할 임시 배열

    // 배열을 순회하며 각 숫자의 발생 빈도 계산
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 누적합을 계산하여 각 숫자가 배치될 인덱스 구간 확인
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // 원본 배열을 역순으로 순회하며 위치 배정 (안정 정렬 유지를 위함)
    for (int i = n - 1; i >= 0; i--) {
        int x = arr[i]; // 현재 배치할 숫자
        int pos = count[x] - 1; // 누적합을 통해 얻은 배치 인덱스
        ret[pos] = x; // 결과 배열에 삽입
        count[x]--; // 다음 동일한 숫자는 앞자리에 배치하도록 인덱스 감소
    }

    // 정렬된 결과를 원본 배열에 복사
    for (int i = 0; i < n; i++) {
        arr[i] = ret[i];
    }
}