C; 배열 정렬 알고리즘 (버블 정렬, 삽입정렬, 퀵 정렬, 힙 정렬, 병합 정렬)

 

 

 

 

배열을 정렬하는 알고리즘은 많다.

그중에서도 유명한 정렬 방법들 몇 개를 설명하겠다.

 

1. 버블 정렬 (Bubble Sort)

• 평균 시간 복잡도: $O(n^2)$
• 특징: 매우 단순하고 이해하기 쉬운 정렬 알고리즘임. 효율성 측면에서 매우 비효율적. 배열의 크기가 큰 경우 매우 느림.

코드:

#include <stdio.h>

void ascBubbleSort(int arr[], int len);
void desBubbleSort(int arr[], int len);
void printArray(int arr[], int size);

int main() {
    int arr[10] = {1, 5, 2, 9, 7, 8, 3, 10, 6, 4};
    int arrLen = sizeof(arr) / sizeof(int);
	
    printf("정렬 전 배열: \n");
    printArray(arr, arrLen);
    
    ascBubbleSort(arr, arrLen);
    printf("오름차순 정렬: \n");
    printArray(arr, arrLen);

    desBubbleSort(arr, arrLen);
    printf("내림차순 정렬: \n");
    printArray(arr, arrLen);
    return 0;
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void ascBubbleSort(int arr[], int len) {
    int temp;

    for (int i = 0; i < len - 1; i++)
        for (int j = 0; j < (len - i) - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
}

void desBubbleSort(int arr[], int len) {
    int temp;

    for (int i = 0; i < len - 1; i++)
        for (int j = 0; j < (len - i) - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
}

 

2. 삽입 정렬 (Insertion Sort)

• 평균 시간 복잡도: $O(n^2)$ , 배열이 거의 정렬된 경우 평균 시간 복잡도는 $O(n)$
• 특징: 크기가 작은 배열이나 거의 정렬된 배열에서는 효율적임.

코드:

#include <stdio.h>

void insertionSort(int arr[], int len);
void printArray(int arr[], int len);

int main() {
    int arr[10] = {1, 5, 2, 9, 7, 8, 3, 10, 6, 4};
    int arrLen = sizeof(arr) / sizeof(int);

    printf("정렬 전 배열: \n");
    printArray(arr, arrLen);

    insertionSort(arr, arrLen);

    printf("\n정렬 후 배열: \n");
    printArray(arr, arrLen);
    return 0;
}

void insertionSort(int arr[], int len) {
    for (int i = 1; i < len; 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;
    }
}

void printArray(int arr[], int len) {
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

 

3. 퀵 정렬 (Quick Sort)

• 평균 시간 복잡도: $O(n\,log\,n)$ , 최악의 경우에는 $O(n^2)$이나, 적절한 피벗 선택을 통해 해결 가능.
• 특징: 분할 정복 알고리즘으로 배열을 분할하여 정렬함. 일반적으로 매우 빠른 방법임

코드:

#include <stdio.h>

void swap(int *a, int *b);
int partition(int arr[], int size);
void quickSort(int arr[], int size);
void printArray(int arr[], int size);

int main() {
    int arr[10] = {1, 5, 2, 9, 7, 8, 3, 10, 6, 4};
    int arrLen = sizeof(arr) / sizeof(int);

    printf("정렬 전 배열: \n");
    printArray(arr, arrLen);

    quickSort(arr, arrLen);

    printf("\n정렬 후 배열: \n");
    printArray(arr, arrLen);
    return 0;
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int size) {
    int pivot = arr[size - 1];
    int i = -1;

    for (int j = 0; j < size - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[size - 1]);
    return (i + 1);
}

void quickSort(int arr[], int size) {
    if (size > 1) {
        int pi = partition(arr, size);

        quickSort(arr, pi);
        quickSort(arr + pi + 1, size - pi - 1);
    }
}

 

4. 힙 정렬 (Heap Sort)

• 시간 복잡도: $O(n\,log\,n)$
• 특징: 힙 자료 구조를 이용한 정렬. 최악의 경우에도 시간복잡도 $O(n\,log\,n)$ 보장함.

코드:

#include <stdio.h>

void swap(int *a, int *b);
void heapify(int arr[], int n, int i);
void heapSort(int arr[], int n);
void printArray(int arr[], int n);

int main() {
    int arr[10] = {1, 5, 2, 9, 7, 8, 3, 10, 6, 4};
    int arrLen = sizeof(arr) / sizeof(int);

    printf("정렬 전 배열: \n");
    printArray(arr, arrLen);

    heapSort(arr, arrLen);

    printf("\n정렬 후 배열: \n");
    printArray(arr, arrLen);
    return 0;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    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(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

5. 병합 정렬 (Heap Sort)

 

• 시간 복잡도: $O(n\,log\,n)$
• 특징: 분할 정복 알고리즘으로 배열을 반으로 나누어 정렬 후 병합. 안정적인 정렬 알고리즘.

코드:

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

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);
void printArray(int arr[], int size);

int main() {
    int arr[10] = {1, 5, 2, 9, 7, 8, 3, 10, 6, 4};
    int arrLen = sizeof(arr) / sizeof(int);

    printf("정렬 전 배열: \n");
    printArray(arr, arrLen);

    mergeSort(arr, 0, arrLen - 1);

    printf("\n정렬 후 배열: \n");
    printArray(arr, arrLen);
    return 0;
}

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

    int L[n1], R[n2];

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

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

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

 

결론

 

정렬 방법	시간 복잡도
버블 정렬	$O(n^2)$
삽입 정렬	$O(n^2)$ ~ $O(n)$
퀵 정렬	$O(n^2)$ ~ $O(n\,log\,n)$
힙 정렬	$O(n\,log\,n)$
병합 정렬	$O(n\,log\,n)$