정렬

기술노트

정렬

정렬 알고리즘은 데이터 요소를 특정 순서(일반적으로 오름차순 또는 내림차순)로 배열하는 알고리즘입니다. 이는 컴퓨터 과학에서 가장 기본적이고 중요한 문제 중 하나로, 다양한 응용 프로그램에서 폭넓게 사용됩니다.

주요 정렬 알고리즘

버블 정렬(Bubble Sort)

  • 개념: 인접한 두 원소를 비교하여 필요시 교환하는 과정을 반복하는 간단한 정렬 알고리즘
  • 작동 방식:
    1. 배열을 순회하며 인접한 두 원소를 비교
    2. 왼쪽 원소가 오른쪽 원소보다 크면 두 원소 교환
    3. 배열의 끝까지 도달하면 가장 큰 원소가 맨 오른쪽에 위치
    4. 이 과정을 배열이 정렬될 때까지 반복
  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 특징: 안정적인 정렬 알고리즘, 구현이 간단, 작은 데이터셋에 적합
void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 교환
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

선택 정렬(Selection Sort)

  • 개념: 현재 위치에 들어갈 값을 찾아 교환하는 정렬 알고리즘
  • 작동 방식:
    1. 정렬되지 않은 부분에서 최소값(또는 최대값) 찾기
    2. 이 값을 정렬되지 않은 부분의 첫 번째 원소와 교환
    3. 정렬된 부분을 한 원소씩 늘려가며 전체가 정렬될 때까지 반복
  • 시간복잡도: O(n²)
  • 공간복잡도: O(1)
  • 특징: 불안정 정렬 알고리즘, 교환 횟수가 적음, 작은 데이터셋에 적합
void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 최소값을 현재 위치와 교환
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

삽입 정렬(Insertion Sort)

  • 개념: 현재 값을 이미 정렬된 부분의 적절한 위치에 삽입하는 정렬 알고리즘
  • 작동 방식:
    1. 두 번째 원소부터 시작하여 이전 원소들과 비교
    2. 자신의 위치를 찾을 때까지 이전 원소들을 뒤로 이동
    3. 적절한 위치에 현재 원소 삽입
    4. 배열의 끝까지 이 과정 반복
  • 시간복잡도: 평균/최악 O(n²), 최선 O(n)
  • 공간복잡도: O(1)
  • 특징: 안정적인 정렬 알고리즘, 작은 데이터셋이나 거의 정렬된 데이터에 효율적
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;
    }
}

병합 정렬(Merge Sort)

  • 개념: 분할 정복 방식을 사용하는 정렬 알고리즘
  • 작동 방식:
    1. 배열을 절반으로 분할(Divide)
    2. 각 부분 배열을 재귀적으로 정렬(Conquer)
    3. 정렬된 부분 배열을 병합(Merge)
  • 시간복잡도: O(n log n)
  • 공간복잡도: O(n)
  • 특징: 안정적인 정렬 알고리즘, 대용량 데이터 처리에 효율적, 추가 메모리 필요
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        
        // 분할
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // 병합
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 임시 배열 생성
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // 데이터 복사
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    // 병합
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 남은 요소 복사
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

퀵 정렬(Quick Sort)

  • 개념: 분할 정복 방식을 사용하는 정렬 알고리즘으로, 피벗을 기준으로 배열 분할
  • 작동 방식:
    1. 배열에서 피벗(pivot) 원소 선택
    2. 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할(Partition)
    3. 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 적용
  • 시간복잡도: 평균 O(n log n), 최악 O(n²)
  • 공간복잡도: O(log n)
  • 특징: 불안정 정렬 알고리즘, 실제 구현에서 매우 빠른 성능, 피벗 선택이 중요
void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 분할 위치
        int pivotIndex = partition(arr, low, high);
        
        // 분할된 부분 배열 정렬
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // 교환
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // 피벗 위치 교환
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

힙 정렬(Heap Sort)

  • 개념: 힙 자료구조를 이용한 정렬 알고리즘
  • 작동 방식:
    1. 배열을 최대 힙(Max Heap)으로 구성
    2. 루트(최대값)를 배열의 맨 끝 원소와 교환
    3. 힙 크기를 줄이고 새 루트를 힙 속성을 만족하도록 조정(heapify)
    4. 힙이 비어질 때까지 2-3 단계 반복
  • 시간복잡도: O(n log n)
  • 공간복잡도: O(1)
  • 특징: 불안정 정렬 알고리즘, 제자리 정렬(in-place), 대용량 데이터 처리에 적합
void heapSort(int[] arr) {
    int n = arr.length;
    
    // 최대 힙 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // 힙에서 원소를 하나씩 추출
    for (int i = n - 1; i > 0; i--) {
        // 현재 루트를 맨 끝으로 이동
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 줄어든 힙에 대해 heapify 호출
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i; // 루트를 최대값으로 초기화
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    // 왼쪽 자식이 루트보다 크다면
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    // 오른쪽 자식이 현재 최대값보다 크다면
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    // 루트가 최대값이 아니라면
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        
        // 영향 받은 서브트리에 대해 재귀적으로 heapify
        heapify(arr, n, largest);
    }
}

정렬 알고리즘 비교

알고리즘 시간복잡도(최선) 시간복잡도(평균) 시간복잡도(최악) 공간복잡도 안정성
버블 정렬 O(n) O(n²) O(n²) O(1) 안정
선택 정렬 O(n²) O(n²) O(n²) O(1) 불안정
삽입 정렬 O(n) O(n²) O(n²) O(1) 안정
병합 정렬 O(n log n) O(n log n) O(n log n) O(n) 안정
퀵 정렬 O(n log n) O(n log n) O(n²) O(log n) 불안정
힙 정렬 O(n log n) O(n log n) O(n log n) O(1) 불안정

정렬 알고리즘 선택 기준

데이터셋 크기

  • 작은 데이터셋: 삽입 정렬, 버블 정렬 등 간단한 알고리즘 적합
  • 큰 데이터셋: 퀵 정렬, 병합 정렬, 힙 정렬 등 효율적인 알고리즘 필요

데이터 특성

  • 거의 정렬된 데이터: 삽입 정렬이 효율적
  • 무작위 데이터: 퀵 정렬이 일반적으로 좋은 성능
  • 역순으로 정렬된 데이터: 퀵 정렬은 피벗 선택에 따라 최악의 성능, 병합 정렬이 적합

메모리 제약

  • 메모리 제한적: 제자리 정렬(in-place)인 퀵 정렬, 힙 정렬 선호
  • 추가 메모리 사용 가능: 병합 정렬 등 사용 가능

안정성 요구

  • 안정성 필요: 병합 정렬, 삽입 정렬 선택
  • 안정성 불필요: 퀵 정렬, 힙 정렬 사용 가능

고급 정렬 알고리즘

팀소트(Timsort)

  • 파이썬과 자바의 기본 정렬 알고리즘
  • 병합 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘
  • 실제 데이터에서 매우 효율적

카운팅 정렬(Counting Sort)

  • 정수 정렬에 특화된 비교 기반이 아닌 정렬 알고리즘
  • 시간복잡도: O(n + k) (k는 값의 범위)
  • 제한된 범위의 정수 정렬에 매우 효율적

기수 정렬(Radix Sort)

  • 낮은 자리 숫자부터 비교하여 정렬하는 비교 기반이 아닌 정렬 알고리즘
  • 시간복잡도: O(d * (n + k)) (d는 최대 자릿수, k는 기수)
  • 정수나 문자열 정렬에 효과적

셸 정렬(Shell Sort)

  • 삽입 정렬의 개선 버전으로, 간격(gap)을 두고 부분 집합을 정렬 후 간격을 줄이는 방식
  • 시간복잡도: 간격 시퀀스에 따라 다름(일반적으로 O(n log²n))
  • 중간 크기의 배열에 효과적

정렬 알고리즘의 응용

  • 데이터베이스: 쿼리 결과 정렬
  • 검색 엔진: 검색 결과 랭킹
  • 컴퓨터 그래픽: Z-버퍼링 등 깊이 정렬
  • 데이터 분석: 통계 처리, 이상치 탐지
  • 압축 알고리즘: 허프만 코딩 등에서 사용
  • 네트워크 라우팅: 패킷 우선순위 결정

관련 항목