글 읽기 - c언어 quick sort 시간초과

royalex 1년 전 0

quick sort를 짜서 돌리면 시간초과가 나옵니다. quick sort 대신에 내장된 qsort를 이용하니 맞았다고 합니다. 둘 다 퀵소트일텐데 왜 시간이 다르게 나오는 지 이유를 아시는 분 있을까요?

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

typedef struct coordinate* coordinateptr;
typedef struct coordinate
{
    int x;
    int y;
} coordinate;

coordinateptr cp;

int partition(int p, int r)
{
    int  h=p, k;
    coordinate temp, pivot= {(cp+p)->x,(cp+p)->y};
    for(k=p+1; k<=r; k++)
    {
        if((&cp[k])->x < pivot.x)
        {
            h=h+1;
            temp=cp[h];
            cp[h]=cp[k];
            cp[k]=temp;
        }
        else if((&cp[k])->x == pivot.x)
        {
            if((&cp[k])->y < pivot.y)
            {
                h=h+1;
                temp=cp[h];
                cp[h]=cp[k];
                cp[k]=temp;
            }
        }
    }
    temp=cp[p];
    cp[p]=cp[h];
    cp[h]=temp;
    return h;
}

void quick_sort(int p, int r)
{
    int q;
    if(p<r)
    {
        q=partition(p,r);
        quick_sort(p, q-1);
        quick_sort(q+1, r);
    }
}

int main()
{
    int n, i;
    scanf("%d", &n);
    cp = malloc(sizeof(coordinate)*n);
    for(i=0; i<n; i++)
    {
        scanf("%d %d", &((cp+i)->x),&((cp+i)->y));
    }
    quick_sort(0, n-1);
    for(i=0; i<n; i++)
    {
        printf("%d %d\n", (cp+i)->x, (cp+i)->y);
    }
    free(cp);
    return 0;
}

zenith82114 1년 전 0

pivot을 랜덤하지 않게 (맨 처음이나 맨 끝 등) 고르는 코드를 저격하기 위한 채점 데이터가 있는 것으로 알고 있습니다.

komjun 1년 전 0

glibc/stdlib/qsort.c 를 확인하면 median-of-three decision tree 를 이용하여 pivot을 선택한다고 하네요

0000000000 1년 전 1

qsort()는 이름만 Quick Sort에서 따 왔을 뿐이지 Quick Sort로 구현되어 있다고 보장되지는 않습니다.

https://en.cppreference.com/w/cpp/algorithm/qsort에서 Notes 부분에 "Despite the name, C++, C, and POSIX standards do not require this function to be implemented using quicksort or make any complexity or stability guarantees." 라고 쓰여 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어 quick sort 시간초과

royalex 1년 전 0

zenith82114 1년 전 0

royalex 1년 전 0

komjun 1년 전 0

0000000000 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말