기본 정렬의 원리와 시간복잡도 비교#

선택 정렬 (Selection Sort)#

원리
선택 정렬은 매우 직관적인 정렬 알고리즘! 배열에서 가장 작은(또는 가장 큰) 원소를 찾아 첫 번째 위치와 교환한 후, 남은 부분 배열에서 같은 과정을 반복하는 방식으로 작동

동작 과정#

정렬되지 않은 부분에서 최솟값(또는 최댓값)을 찾기
이 값을 현재 위치(정렬되지 않은 부분의 첫 번째 위치)와 교환
정렬된 부분을 한 칸 확장하고, 정렬되지 않은 부분을 한 칸 축소
정렬되지 않은 부분이 없어질 때까지 1-3 과정을 반복

예시 코드

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n-1; i++) {
        // 최솟값의 인덱스 찾기
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        
        // 최솟값을 현재 위치로 교환
        swap(arr[min_idx], arr[i]);
    }
}

시간 복잡도: 항상 O(n²)
공간 복잡도: O(1) (제자리 정렬)
안정성: 불안정 (기본 구현에서)
장점: 구현이 단순하고, 교환 연산 횟수가 적음 (최대 n-1회)
단점: 배열 크기에 관계없이 항상 O(n²) 시간이 걸림

버블 정렬 (Bubble Sort)#

원리
버블 정렬은 인접한 두 원소를 비교하여 필요시 위치를 교환하는 과정을 반복! 매 패스마다 가장 큰(또는 작은) 원소가 배열의 끝으로 “버블링(bubbling)“되는 모습이 특징

동작 과정#

인접한 두 원소를 비교
순서가 잘못되어 있으면 두 원소를 교환
배열의 끝까지 이 과정을 반복 (첫 패스 후에는 가장 큰 원소가 마지막 위치에 정렬됨)
배열 크기를 1 감소시키고 1-3 과정을 반복
교환이 더 이상 일어나지 않으면 정렬이 완료!

예시 코드

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        
        // 각 패스에서 인접 원소 비교 및 교환
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        
        // 교환이 일어나지 않았다면 이미 정렬된 상태
        if (!swapped)
            break;
    }
}

시간 복잡도: 평균 및 최악 O(n²), 최선 O(n) (이미 정렬된 경우)
공간 복잡도: O(1) (제자리 정렬)
안정성: 안정적
장점: 구현이 매우 간단하고, 이미 정렬된 데이터에 대해 최적화 가능
단점: 대체로 다른 정렬 알고리즘보다 느림

삽입 정렬 (Insertion Sort)#

원리
삽입 정렬은 카드 게임을 할 때 손에 든 카드를 정렬하는 방식과 유사! 정렬되지 않은 부분에서 원소를 하나씩 가져와 이미 정렬된 부분의 적절한 위치에 삽입하는 방식으로 작동

동작 과정#

두 번째 원소부터 시작(첫 번째 원소는 이미 정렬된 것으로 간주)
현재 원소를 이미 정렬된 부분 배열과 비교
정렬된 배열에서 현재 원소보다 큰 모든 원소를 한 칸씩 오른쪽으로 이동
적절한 위치에 현재 원소를 삽입
배열의 모든 원소에 대해 2-4 과정을 반복
완료!

예시 코드

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    
    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;
    }
}

시간 복잡도: 평균 및 최악 O(n²), 최선 O(n) (이미 정렬된 경우)
공간 복잡도: O(1) (제자리 정렬)
안정성: 안정적
장점: 작은 데이터셋에서 효율적, 거의 정렬된 데이터에 매우 빠름, 온라인 알고리즘(데이터가 실시간으로 들어와도 정렬 가능)
단점: 큰 데이터셋에서는 비효율적

종류	평균 시간 복잡도	최선 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성	적응성
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	불안정	아니오
버블 정렬	O(n²)	O(n)	O(n²)	O(1)	안정적	예
삽입 정렬	O(n²)	O(n)	O(n²)	O(1)	안정적	예

적응성?
이미 부분적으로 정렬된 배열에 대해 더 좋은 성능을 보이는지 여부

안정성?
선택 정렬을 예시로 들어보자
선택 정렬은 불안정 정렬이다! 제일 작은 값을 찾은 후 교환(어느 위치에 있던지, 교환됨)하기 때문이다. 교환을 통해서 순서가 고려되지 못하기 때문에 안정적으로 정렬되지 않는다.(기본 구현에서는 이렇구 따로 고려하여 작성하면 해결 가능)

고급 정렬의 원리와 시간복잡도 비교#

병합 정렬 (Merge Sort)#

원리
병합 정렬은 ‘분할 정복(divide and conquer)’ 방식을 사용 배열을 절반으로 나누고, 각 절반을 재귀적으로 정렬한 다음, 정렬된 두 절반을 병합

동작 과정#

분할(Divide)
- 배열을 절반으로 계속해서 나눕니다. 이 과정은 더 이상 나눌 수 없을 때까지(요소가 1개만 남을 때까지) 재귀적으로 진행
정복(Conquer)
- 크기가 1인 부분 배열은 이미 정렬된 상태로 간주합니다. 이는 기저 사례(base case)입니다
병합(Merge)
- 나누어진 부분 배열들을 정렬된 상태로 병합합니다
- 1. 두 부분 배열의 첫 번째 요소부터 비교
  2. 더 작은 값을 결과 배열에 넣고, 해당 배열의 포인터를 다음 요소로 이동
  3. 이 과정을 한 배열이 모두 소진될 때까지 반복
  4. 남은 요소들을 결과 배열에 차례대로 추가

예시 코드

int A[1'000'005], N;

void Merge(int s1, int e1, int s2, int e2){
    vector<int> tmp;
    int idx_1 = s1, idx_2 = s2;
    while (idx_1 <= e1 || idx_2 <= e2){
        if (idx_1 > e1) tmp.push_back(A[idx_2++]);
        else if (idx_2 > e2) tmp.push_back(A[idx_1++]);
        else if (A[idx_1] < A[idx_2]) tmp.push_back(A[idx_1++]);
        else tmp.push_back(A[idx_2++]);
    }
    
    for (int i = 0; i < tmp.size(); i++) A[s1 + i] = tmp[i];
}

void MergeSort(int s, int e){
    if (s == e) return;
    int mid = (s+e) / 2;
    MergeSort(s, mid);
    MergeSort(mid+1, e);
    Merge(s, mid, mid+1, e);
}

시간 복잡도: 항상 O(n log n)
공간 복잡도: O(n)
안정성: 안정적 (동일한 값의 상대적 순서 유지)
최적 사용 사례: 연결 리스트 정렬, 대용량 데이터 정렬
장점: 일관된 성능, 안정적, 데이터 분포에 영향 받지 않음
단점: 추가 메모리 공간 필요, 작은 데이터셋에는 비효율적

퀵 정렬(Quick Sort)#

원리
퀵 정렬도 분할 정복 방식을 사용하지만, 피벗(pivot)이라는 요소를 기준으로 배열을 분할 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동시킨 후 각 부분 배열을 재귀적으로 정렬

동작 과정#

피벗 선택(Select a Pivot)
- 배열에서 하나의 요소를 피벗(pivot)으로 선택 피벗 선택
  방법은 다양하지만, 일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택
분할(Partition)
- 피벗을 기준으로 배열을 두 부분으로 재배치
- 1. 피벗보다 작은 모든 요소는 피벗의 왼쪽으로 이동
  2. 피벗보다 큰 모든 요소는 피벗의 오른쪽으로 이동
  3. 분할 후 피벗은 최종 위치에 놓이게 됩니다
재귀적 정렬(Recursive Sort)

피벗의 왼쪽과 오른쪽 부분 배열에 대해 1단계와 2단계를 재귀적으로 적용
부분 배열의 크기가 1 이하일 때 재귀를 종료

예시 코드

```cpp
int partition(vector<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++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 피벗의 최종 위치 반환
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 배열 분할
        int pi = partition(arr, low, high);
        
        // 분할된 부분 배열 정렬
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

시간 복잡도: 평균 O(n log n), 최악 O(n²)
공간 복잡도: O(log n) (재귀 호출 스택)
안정성: 불안정
최적 사용 사례: 평균적인 케이스, 작은-중간 크기 배열
장점: 실제 구현에서 빠른 성능, 작은 추가 메모리
단점: 최악의 경우 성능 저하, 이미 정렬된 데이터에 취약

힙 정렬 (Heap Sort)#

원리
힙 정렬은 이진 힙 자료구조를 이용! 먼저 배열을 최대 힙(부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리)으로 구성한 다음, 루트(최댓값)를 배열의 끝으로 이동시키고 힙 크기를 줄여가며 과정을 반복

동작 과정#

힙 구성(Build Heap)
- 주어진 배열을 최대 힙으로 구성
  배열의 중간부터 시작하여 루트까지 각 노드에 대해 ‘힙화(heapify)’ 연산을 수행함으로써 이루어집니다.
요소 추출 및 힙 재구성(Extract and Rebuild)
- 1. 힙의 루트(최댓값)를 배열의 마지막 위치와 교환
  2. 힙의 크기를 1 감소(마지막 요소는 이제 정렬된 부분에 속합니다)
  3. 새로운 루트에 대해 ‘힙화’ 연산을 수행하여 최대 힙 속성을 복원
  4. 힙의 크기가 1이 될 때까지 이 과정을 반복
’힙화(Heapify)’ 연산
- ’힙화’는 특정 노드부터 시작하여 해당 노드가 자식 노드보다 작다면 자식 중 가장 큰 노드와 교환하고, 이 과정을 재귀적으로 반복하는 연산

예시 코드

```cpp
void heapify(vector<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) {
        swap(arr[i], arr[largest]);
        
        // 영향 받은 서브트리에 대해 재귀적으로 heapify 실행
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // 최대 힙 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // 힙에서 요소를 하나씩 추출
    for (int i = n - 1; i > 0; i--) {
        // 현재 루트를 끝으로 이동
        swap(arr[0], arr[i]);
        
        // 줄어든 힙에 대해 heapify 호출
        heapify(arr, i, 0);
    }
}

시간 복잡도: 항상 O(n log n)
공간 복잡도: O(1) (제자리 정렬)
안정성: 불안정
최적 사용 사례: 메모리 제약이 있는 환경, 최악 시간 복잡도 보장이 필요한 경우
장점: 추가 메모리 불필요, 최악의 경우도 O(n log n) 보장
단점: 실제 구현에서 캐시 효율성이 낮음, 평균적으로 퀵 정렬보다 느림

종류	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성	제자리 정렬
병합 정렬	O(n log n)	O(n log n)	O(n)	안정적	아니오
퀵 정렬	O(n log n)	O(n²)	O(log n)	불안정	예
힙 정렬	O(n log n)	O(n log n)	O(1)	불안정	예

그러면 이제 메인 과제 Radix Sort(기수 정렬)에 대해서 알아봅시다.

Radix Sort(기수 정렬)#

라딕스 정렬은 비교 기반이 아닌 정렬 알고리즘으로, 데이터의 각 자릿수를 기준으로 정렬을 수행! 이 정렬 방식은 특히 정수나 문자열과 같이 자릿수가 있는 데이터에 효과적입니둥

작동 원리#

데이터의 가장 작은 자릿수(일의 자리)부터 시작하여 가장 큰 자릿수까지 정렬
각 자릿수별로 안정적인 정렬 알고리즘(보통 계수 정렬)을 사용
각 단계에서 정렬된 결과는 다음 자릿수 정렬의 입력으로 사용

특징#

시간 복잡도: O(d × n), 여기서 d는 최대 자릿수, n은 정렬할 요소의 개수입니다.
공간 복잡도: O(n + k), 여기서 k는 숫자 체계의 기수(예: 십진수에서는 10)입니다.
안정적인 정렬
비교 기반 정렬이 아니므로 이론적 하한인 O(n log n)을 뛰어넘을 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 특정 자릿수를 기준으로 계수 정렬을 수행하는 함수
void countSort(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n); // 결과를 저장할 배열
    vector<int> count(10, 0); // 0-9의 발생 횟수를 저장할 배열
    
    // 현재 자릿수에 해당하는 숫자의 발생 횟수 계산
    for (int i = 0; i < n; i++) 
        count[(arr[i] / exp) % 10]++;
    
    
    // count 배열을 누적합으로 변환
    for (int i = 1; i < 10; i++) 
        count[i] += count[i - 1];
    
    
    // 뒤에서부터 순회하여 출력 배열 구성 (안정적 정렬을 위해)
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    // 원래 배열에 정렬된 결과 복사
    for (int i = 0; i < n; i++) 
        arr[i] = output[i];
    
}

void radixSort(vector<int>& arr) {
    // 배열에서 최댓값 찾기
    int maxVal = *max_element(arr.begin(), arr.end());
    
    // 각 자릿수에 대해 계수 정렬 수행
    for (int exp = 1; maxVal / exp > 0; exp *= 10) 
        countSort(arr, exp);
    
}

void print(const vector<int>& arr) {
    for (int num : arr) 
        cout << num << " ";
    
    cout << endl;
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    
    cout << "정렬 전 배열: ";
    print(arr);
    
    radixSort(arr);
    
    cout << "정렬 후 배열: ";
    print(arr);
    
    return 0;
}

계수 정렬(countSort)#

특정 자릿수에 대해 계수 정렬을 수행
해당 자릿수의 숫자(0-9)의 발생 횟수를 계산
누적합을 이용해 각 숫자의 최종 위치를 결정
안정적인 정렬을 위해 배열을 뒤에서부터 순회

라딕스 정렬(radixSort)#

배열에서 최댓값을 찾아 자릿수를 결정
일의 자리부터 시작하여 각 자릿수에 대해 계수 정렬을 수행
자릿수는 10의 거듭제곱으로 표현(exp = 1, 10, 100, …)

장점#

큰 범위의 정수를 효율적으로 정렬 가능
자릿수가 제한적인 경우 O(n) 시간 복잡도로 동작할 수 있음
비교 연산을 사용하지 않아 특정 상황에서 빠른 성능

단점#

추가 메모리가 필요
음수 처리를 위해서는 추가 로직이 필요
부동 소수점 숫자를 정렬하려면 알고리즘을 수정

감사합니다!