오름차순으로 수 정렬하기

수 n개가 주어졌을 때, ( 1 <= n <= 10,000,000 ) 오름차순으로 정렬 하는 프로그램을 작성하라.

n개 수의 값들은 10,000보다 작거나 같은 값들이다.

이 프로그램을 보면 배열의 크기를 10,000,000의 크기로 잡고, 퀵 정렬(Quick Sort)을 이용해서 정렬을 마무리 한 뒤,

출력을 차례대로 하면 되겠구나 생각하였다.

하지만 이런식의 코딩을 하게 되면 큰 오류를 범하게 되는데,

arr의 배열이 int당 4byte라 치면 40,000,000byte -> 39062kbyte -> 38mb라는 큰 메모리를 요구하게 된다.

이는 메모리를 과용하는 일이므로 좋지 못한 알고리즘을 가진 프로그램이 될 수 있다.

#include <stdio.h>
 
 
int arr[10000002];
 
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;
int i;
 
scanf("%d",&n);
 
 
for(i = 0 ; i < n ; i++ ){ scanf("%d",&arr[i]);}
 
QuickSort(arr,0,n-1);
 
for(i = 0 ; i < n ; i++ ){ printf("%d ",arr[i]); }
 
 
}
 
 

따라서 다음과 같은 문제는 아래의 알고리즘과 같은 방법으로 해결 할 수 있다.

#include <stdio.h>
 
#define INDEX 10001
 
int main()
{
    int count, i, j, k;
    int arry[INDEX] = {0,};
    scanf("%d", &count);
    
    for(i = 0; i < count; i++)
    {
        scanf("%d", &k);
        arry[k] = arry[k] + 1;
    }
 
    for(i = 1; i < INDEX; i++ )
    {
        if(arry[i] != 0)
        {
            for(j = 0; j < arry[i]; j++)
            printf("%d\n", i);
        }
    }
 
}
 

이 알고리즘은 알게 되면 쉽지만,

막상 처음 접하시는 분들은 생각하기가 까다로울 수도 있다.

알고리즘에 대해서 설명하자면

INDEX는 배열 arry[]가 가질 수 있는 값의 범위이자 배열의 크기라 볼 수 있다.

arry[] = arry[] + 1;의 의미는

scanf로 만약 1을 받으면 arry[1]에 1을 더하라는 것, 즉 1번 배열에 1을 더하라는 것이다.

즉, n번 배열에 n을 더하면 되는 것이니. 1이 몇개인지 2가 몇개인지 ... 10000까지의 개수를 배열의 번호에 있는 값으로 파악 할 수 있다.

마지막 if(arry[i] != 0)은 이제 scanf로 받은 적이 없는 값들을 걸러내는 작업이라고 보면 된다.

단순한 수 정렬 문제로써 퀵정렬로 해결하면 되는것 처럼 보일지 모르지만, 

조금 더 생각해보면 이런 알고리즘이 있듯이, 아직 생각지 못한 이보다 더 좋은 알고리즘도 있을지도 모른다..