C언어 모든 정렬 알고리즘 가장 간단한 코드 정리 (순차, 버블, 삽입, 선택, 병합, 퀵 정렬)

C언어 정렬 알고리즘을 매번 다른 형식으로 작성하기 귀찮아서 정형화시켜 정리합니다.

대부분의 코드를 가장 보기 편하고 단순한 형태로 작성하였습니다.

 

이 포스트에 포함되는 정렬 알고리즘은 순차 정렬(Sequential Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)입니다.

 

정렬 알고리즘은 크게 O(n^2) 시간에 수행 가능한 알고리즘과 O(n log n)시간에 수행 가능한 알고리즘으로 분류됩니다.

O(n^2) 알고리즘 : 순차 정렬, 버블 정렬, 삽입 정렬, 선택 정렬

O(n log n) 알고리즘 : 병합 정렬, 퀵 정렬

 

 

순차 정렬 (Sequential Sort)

#include<stdio.h>

int main() {
    int arr[100], n, temp;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

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

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

 

순차 정렬은 j가 뒤로 가면서 i번째 원소보다 작은 값이 나오면 수시로 바꿔주는 정렬 방법입니다.

 

 

버블 정렬 (Bubble Sort)

#include<stdio.h>

int main() {
    int arr[100], n, temp;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

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

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

 

버블 정렬은 인접한 숫자들을 비교하면서 위치를 바꿔나가는 정렬입니다.

 

 

삽입 정렬 (Insertion Sort)

#include<stdio.h>

int main() {
    int arr[100], n, temp;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

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

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

 

삽입 정렬은 key 값(위의 코드에서는 temp)을 잡고 key 값이 들어갈 찾아 하나씩 대입해서 정렬하는 방법입니다.

 

 

선택 정렬 (Selection Sort)

#include<stdio.h>

int main() {
    int arr[100], n, temp;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

    int min;
    for(int i=0; i<n; i++) {
        min = i;
        for(int j=i; j<n; j++) if(arr[j] < arr[min]) min = j;
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }

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

 

선택 정렬은 남은 원소들 중에서 최솟값을 찾아서 앞으로 보내면서 정렬하는 방법입니다.

 

 

병합 정렬 (Merge Sort)

#include<stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int arrCopy[100], i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(arr[i] <= arr[j]) arrCopy[k++] = arr[i++];
        else arrCopy[k++] = arr[j++];
    }
    while(i<=mid) arrCopy[k++] = arr[i++];
    while(j<=right) arrCopy[k++] = arr[j++];
    for(int a=left; a<=right; a++) arr[a] = arrCopy[a];
}

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

int main() {
    int arr[100], n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

    mergeSort(arr, 0, n-1);

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

 

병합 정렬은 원소들을 그룹으로 계속 나눈 뒤, 다시 합치면서 크기 순으로 정렬하는 방식입니다.

병합 정렬의 경우 최악의 배치로 원소들이 구성되어도 O(n log n) 시간에 정렬이 완료됩니다.

 

 

퀵 정렬 (Quick Sort)

#include<stdio.h>

void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

int partition(int arr[], int left, int right) {
    int pivot = arr[left], low = left+1, high = right, temp;
    while(low <= high) {
        while(low <= right && pivot >= arr[low]) low++;
        while(high >= (left+1) && pivot <= arr[high]) high--;
        if(low <= high) swap(arr, low, high);
    }
    swap(arr, left, high);
    return high;
}

void quickSort(int arr[], int left, int right) {
    if(left <= right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
}

int main() {
    int arr[100], n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);

    quickSort(arr, 0, n-1);

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

 

퀵 정렬 역시 원소들을 그룹들로 나눈 뒤, pivot을 설정하여 이 pivot을 기준으로 원소들을 정렬하는 방법입니다.

퀵 정렬의 경우 평균적으로 O(n log n)의 시간복잡도인 것이지 최악의 경우 O(n^2)의 시간이 걸리기도 합니다.