[C언어 22] 정렬 알고리즘 총 정리: C언어 구현

 

정렬 알고리즘은 데이터의 순서를 특정 기준(오름차순/내림차순)에 따라 배열하는 과정입니다. 백준 2751번 문제(정수 오름차순 정렬)을 활용하여 C 언어로 구현할 수 있는 다양한 정렬 알고리즘을 소개합니다. 각각의 알고리즘은 시간 복잡도와 효율성이 다르므로 상황에 따라 적합한 정렬 방법을 선택해야 합니다.

 

각 정렬 알고리즘에 대한 원리와 특징은 이전 포스트를 참고하면 되겠습니다.

 

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 정렬 알고리즘 총 정리

[자료구조 & 알고리즘] 정렬 알고리즘 총 정리

 

 

---

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 숫자를 비교해가며 자리를 교환하는 방식입니다.

#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;
            }
        }
    }
}

---

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 이미 정렬된 부분 배열에 새 요소를 알맞은 위치에 삽입하는 방식입니다.

#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;
    }
}

---

3. 선택 정렬 (Selection Sort)

선택 정렬은 매번 최소값을 찾아 배열의 앞부분부터 채워나가는 방식입니다.

#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;
    }
}

---

4. 퀵 정렬 (Quick Sort)

직접 구현한 퀵 정렬

퀵 정렬은 분할 정복 기법을 사용하며, 평균적으로 가장 빠른 정렬 알고리즘 중 하나입니다.

#include <stdio.h>

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;

    int pivot = arr[left];
    int i = left + 1;
    int j = right;

    while (i <= j) {
        while (i <= right && arr[i] <= pivot) i++;
        while (j > left && arr[j] >= pivot) j--;
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[left];
    arr[left] = arr[j];
    arr[j] = temp;

    quickSort(arr, left, j - 1);
    quickSort(arr, j + 1, right);
}

표준 라이브러리의 qsort 함수

C의 표준 라이브러리 <stdlib.h>는 **일반화된 퀵 정렬 함수 qsort**를 제공합니다. 이 함수는 정렬 알고리즘을 직접 구현하지 않고도 간단히 사용할 수 있습니다.

사용법

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);  // 오름차순 정렬
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, n, sizeof(int), compare);

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

qsort 함수 설명

• 매개변수:
  1. 정렬할 배열의 시작 주소 (void *base)
  2. 배열 요소의 개수 (size_t nitems)
  3. 각 요소의 크기 (size_t size)
  4. 비교 함수의 포인터 (int (*compar)(const void *, const void *))
• 비교 함수:
  • 두 요소를 비교해, 양수를 반환하면 자리를 교환합니다.
  • 오름차순 정렬: return (*(int *)a - *(int *)b);
  • 내림차순 정렬: return (*(int *)b - *(int *)a);

출력 결과

Sorted array: 1 2 5 5 6 9

---

5. 병합 정렬 (Merge Sort)

병합 정렬은 배열을 나누고 합병하며 정렬하는 방식입니다.

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    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++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

---

6. 기수 정렬 (Radix Sort)

기수 정렬은 자리수별로 정렬하는 비비교 기반 정렬입니다.

#include <stdio.h>

int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

void countSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
    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(int arr[], int n) {
    int max = getMax(arr, n);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.