[11931번] 수 정렬하기 4(Quick Sort, merge Sort, etc.)

문제 출처 :

 

https://www.acmicpc.net/problem/11931

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬 방법

2. 메모리를 이용한 단순 정렬

3. Quick Sort

4. Merge Sort

이 코드를 통해 다양한 정렬 방법을 이용해 보고, 각 정렬 방법에 따라 시간 복잡도 및 공간 복잡도(메모리 사용량)를 확인해본다.

소스코드는 총 3가지(메모리 이용 정렬, 퀵 정렬, 병합 정렬)로 나타낸다.

소스 코드 : 

1. 메모리를 이용한 단순 정렬

이 정렬 방법은 메모리 공간을 많이 이용하는 대신 각 배열의 자신의 값에 해당하는 배열에 1값을 취하여 1인 값을 모두 내림차순으로 출력하면 되는 방식이다.

단, 이코드의 단점은 배열의 크기가 특정 값 이상되면 stack overflow가 일어나므로 이번 문제에서의 조건이 1000만정도의 값이 아니기에 이용 할 수 있었다.

그리고 음수 -1000000은 배열에 arr[-1000000]이 없으므로 1000000을 더하여 arr[0]에 넣도록 하고 1000000은 arr[2000000]에 넣도록 하였다.

#include <stdio.h>
 
int arr[2000002] = { 0, };
 
int main()
{
    int n, i, tmp;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        arr[tmp+1000000] = 1;
    }
 
    for (i = 2000001; i >= 0; i--)
    {
        if (arr[i] == 1)
            printf("%d\n", i-1000000);
    }
 
    return 0;
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>

2. 퀵 정렬(Quick Search)

#include <stdio.h>
 
int arr[1000001];
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 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 n, k, i, j, tmp;
    int cnt = 0;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    QuickSort(arr, 0, n - 1);
 
    for (i = n-1; i >= 0; i--)
        printf("%d\n", arr[i]);
 
    return 0;
}
 
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>

2. 병합 정렬(Merge Search)

** cpp로 제작된 소스 코드입니다. **

#include <stdio.h>
 
int merge(int *ar, int len);
int arr[1000001];
 
int main()
{
    int n, i;
    int cnt = 0;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    merge(arr, n);
 
    for (i = n - 1; i >= 0; i--)
        printf("%d\n", arr[i]);
 
    return 0;
}
 
int merge(int *ar, int len)
{
    if (len < 2) return 0;
 
    int mid = len / 2;
    merge(ar, mid);
    merge(ar + mid, len - mid);
 
    int *buf = new int[len];
 
    int i = 0;
    int j = mid;
    int k = 0;
 
    while (i < mid && j < len)
        buf[k++] = (ar[i] < ar[j]) ? ar[i++] : ar[j++];
 
    while (i < mid)
        buf[k++] = ar[i++];
 
    while (j < len)
        buf[k++] = ar[j++];
 
    for (i = 0; i < len; i++)
        ar[i] = buf[i];
 
    delete[] buf;
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>

각 정렬에 따른 시간 복잡도와 메모리 사용량을 확인한 결과

확실히 퀵 정렬은 빠르고, 메모리 소모도 적었지만,

병합 정렬이 메모리를 이용한 정렬보다 더 최악으로 나타났다.

이 이유는 아마 수가 n의 범위가 100만에 한정되어 있어서 메모리를 이용한 정렬이 더 효율이 좋은 시점이 아니었나 싶다.

1000만으로 넘어간다면 메모리를 이용한 정렬은 쓸 수 없을 뿐더러, 만일 쓰게 되더라도 엄청난 메모리 낭비가 나타날 것이다.