Sorting Algorithms

# Sorting Algorithms

> 버블·선택·삽입·퀵·병합 정렬 C 구현 및 비교

## 학습 목표

- 대표적인 정렬 알고리즘을 C로 직접 구현한다
- 각 정렬의 시간 복잡도를 비교하고 적절한 상황을 판단한다

## 내용

### 버블 정렬 O(n²)

```c
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) { int t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; }
}
```

### 선택 정렬 O(n²)

```c
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) if (arr[j] < arr[min]) min = j;
        int t = arr[i]; arr[i] = arr[min]; arr[min] = t;
    }
}
```

### 퀵 정렬 O(n log n) 평균

```c
int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) { i++; int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
    int t=arr[i+1]; arr[i+1]=arr[hi]; arr[hi]=t;
    return i+1;
}
void quick_sort(int arr[], int lo, int hi) {
    if (lo < hi) { int p=partition(arr,lo,hi); quick_sort(arr,lo,p-1); quick_sort(arr,p+1,hi); }
}
```

### 병합 정렬 O(n log n)

```c
void merge(int arr[], int l, int m, int r) { /* 임시 배열로 병합 */ }
void merge_sort(int arr[], int l, int r) {
    if (l < r) { int m=(l+r)/2; merge_sort(arr,l,m); merge_sort(arr,m+1,r); merge(arr,l,m,r); }
}
```

## 비교표

| 알고리즘 | 최선 | 평균 | 최악 | 안정 |
|---------|------|------|------|------|
| 버블    | O(n) | O(n²)| O(n²)| ✅  |
| 선택    | O(n²)| O(n²)| O(n²)| ❌  |
| 퀵      | O(n log n)| O(n log n)| O(n²)| ❌ |
| 병합    | O(n log n)| O(n log n)| O(n log n)| ✅ |

// COMMENTS

ON THIS PAGE