maxsort (qsort 소트보다 빠른)

n개에서 최상위 또는 최하위 m개를 얻기위해서 일반적으로 사용하는 qsort보다 빠른 소팅 알고리즘에 대해 설명하겠다.

 

10000개의 문자열에서 동적으로 정렬된 10개의 문자열을 얻기 위해서 전체를 정렬하는것 보다 상위 가져오는 개수만큼만을 가지고 있는것이 상식적으로 빠른 방법일것이다.

 

최상위 10개의 값을 얻기 위해 일반적인 qsort 알고리즘을 10000개를 소팅할때 order of 10000log1000정도의 연산이 필요하지만

소개하려는 maxsort를 이용할 경우 10000log10 정도의 연산으로 똑같은 값을 얻을수 있다

 

방법은 간단하게

 

정렬되지 않은 문자열의 최상위 10개를 가져와 정렬하고 11번째 문자열부터 비교를 시작한다.

11번째 문자열이 정렬된 문자열의 마지막 문자열과 비교해서 크면 10개의 문자열안에 들어갈 자격을 얻게되고 그렇지 않을 경우 버린다.

자격을 얻은 문자열은 여러가지 방법이 있겠지만 이진 검색으로 추가할 위치를 찾아 추가한다.

그러면 결과적으로 문자열은 11개가 되고 마지막 1개의 문자열을 버린다.

이와 같은 방법으로 하면 문서를 한번 스캔하면서 최상위 문자열 10개를 얻을수 있다.

 

아래 방법은 이진검색을 하지 않고 간단한 방법론을 이해할수 있게 시퀄셜하게 검색하여 추가하였다.

 

 

#include
#include
#include
#define     MAX 5

int comp(const void*a, const void*b)
{
    char    *str1 = (char*)a;
    char    *str2 = (char*)b;
    return strcmp(str1,str2);
}

 

int     insert(char arr[][1024],char    *buffer);
int main()
{

    FILE    *fp = fopen("input.txt","r");
    FILE    *fw = fopen("result.,txt","w");

    int     i = 0;
    int     ret = 0;
    int     idx = 0;
    int     size = 0;
    char    buffer[1024];
    char    arr[MAX][1024];

    while(fgets(buffer,1024,fp) != NULL)
    {

        size = strlen(buffer);
        if(buffer[size -1] == '\n') buffer[size -1] = '\0';
        strcpy(arr[idx++],buffer);
        if(idx == MAX)  break;
    }

    printf("\nBefore-------------------\n");
    for(i = 0; i < MAX; i++)        printf("[%d]\t%s\n",i,arr[i]);
    qsort(arr,MAX,sizeof(arr[0]),comp);

    printf("\nAfter-------------------\n");
    for(i = 0; i < MAX; i++)        printf("[%d]\t%s\n",i,arr[i]);

    while(fgets(buffer,1024,fp) != NULL)
    {
        size = strlen(buffer);
        if(buffer[size -1] == '\n') buffer[size -1] = '\0';

        ret = strcmp(buffer,arr[4]);

        if(ret == 0)    continue;

        if(ret < 0)
        {
            insert(arr,buffer);
        }
        else
        {
            continue;
        }

    }

    printf("\nFinal-------------------\n");
    for(i = 0; i < MAX; i++)        printf("[%d]\t%s\n",i,arr[i]);
    fclose(fp);
    fclose(fw);
}

int     insert(char arr[][1024],char    *buffer)
{
    int i = 0;
    int idx = 0;
    int ret = 0;

    char    temp[5][1024];
    for(i = 0; i < MAX; i++)
    {

        ret = strcmp(buffer,arr[i]);

        if(ret == 0)
            return 1;
        if(ret < 0)
        {

            strcpy(temp[idx],buffer);
            idx++;
            memcpy(temp[idx],arr[i],sizeof(arr[0])*(MAX-i-1));
            break;
        }
        if(ret  > 0)
        {
            strcpy(temp[idx++],arr[i]);
            continue;
        }
    }
    memcpy(arr,temp,sizeof(arr[0])*MAX);
}

 

input.txt 파일

 

다음

검색

네이버

엔진

형태소

....