[알고리즘 C] 정렬 알고리즘 기본 코드

---

1. 버블 정렬 (Bubble Sort)

특징

• 인접한 두 원소를 비교하며 정렬.
• 시간 복잡도: O(n2)O(n^2).
• 구현이 간단하지만 느림.

코드

#include <stdio.h>

void bubbleSort(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 temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

---

2. 선택 정렬 (Selection Sort)

특징

• 가장 작은 원소를 찾아 맨 앞으로 이동.
• 시간 복잡도: O(n2)O(n^2).
• 교환 횟수가 적음.

코드

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // 현재 최소값의 인덱스
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        // 최소값을 맨 앞으로 이동
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

---

3. 삽입 정렬 (Insertion Sort)

특징

• 이미 정렬된 부분에 새로운 원소를 삽입.
• 시간 복잡도: O(n2)O(n^2), 거의 정렬된 데이터에서 빠름.

코드

#include <stdio.h>

void insertionSort(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;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

---

4. 퀵 정렬 (Quick Sort)

특징

• 분할 정복 방식으로 정렬.
• 시간 복잡도: 평균 O(nlog⁡n)O(n \log n), 최악 O(n2)O(n^2).
• 매우 빠름.

코드

#include <stdio.h>

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);

        quickSort(arr, low, pivot - 1); // 왼쪽 부분
        quickSort(arr, pivot + 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;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

---

5. 병합 정렬 (Merge Sort)

특징

• 분할 정복 방식으로 정렬.
• 시간 복잡도: O(nlog⁡n)O(n \log n).
• 안정적인 정렬 방식.

코드

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    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++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

---

정렬 알고리즘 비교

알고리즘 시간 복잡도 메모리 안정성

버블 정렬	O(n2)O(n^2)	적음	안정적
선택 정렬	O(n2)O(n^2)	적음	불안정
삽입 정렬	O(n2)O(n^2)	적음	안정적
퀵 정렬	O(nlog⁡n)O(n \log n) 평균, O(n2)O(n^2) 최악	적음	불안정
병합 정렬	O(nlog⁡n)O(n \log n)	높음	안정적