조언좀 해주세요

[새내기(191.101)]

unsigned char 10억개 정도를 오름차슌정렬하는 과제인데

시쁠쁠로 작성하래요

실행해서 속도 순으로 점수를 준다고 하는데 quicksort 인가 그거 쓰면 되는 거에요?

[@(1.239)]

내

[mozzart(mozzart)]

10억개? 램이 얼마길래.

[mozzart(mozzart)]

unsigned char 10억개면 카운터 소트 써야지 ㅋㅋ 오늘 내가 낮에 쓴 글 좀 읽어봐.

[mozzart(mozzart)]

정수 배열 256 개 짜리 만들어서 각 문자의 갯수만 세고 순서대로 갯수만큼 출력해주면 끝.

[멍멍이(121.136)]

속도순 채점이면 정렬할 배열을 같은걸 줘야할텐데 그걸 빼돌리고 미리 정렬해가서 출력하도록 하자

[새내기(191.101)]

카운터 소트 우와

[새내기(191.101)]

고맙습니다mozart님

[익명(121.158)]

10억개면 1기가.. 여기서 중요한건 .. 정확한 과제가 뭐냐다. 1기가나 되는 데이타를 소스에 직접 파킹 시킬수는 없고 Data 파일로 제공 될꺼같은데? 입력부터 시간 측정이라면 소팅뿐만아니라 메모리에 데이터 올리기부터 해야되는데 내가 교수라면 실행되는 머신을 메모리 여유분이 1Gb 미만 짜리로 준비해서.. 엿먹이는..

[mozzart(mozzart)]

그냥 카운터 소트가 정답이야 ㅋㅋ stdin 에다 파일 리다이렉션해서 읽어서 출력이겠지.

[밍고스사랑해(mingosudaisuki)]

ㅇㅇ 이거 멍청이 걸러내는 문제임

[밍고스사랑해(mingosudaisuki)]

10억개의 값이 종류가 256가지밖에 안되는데 (CHAR_BIT == 8 기준) comparison sort를 쓰는 건 미개한 짓이고

[밍고스사랑해(mingosudaisuki)]

그냥 0부터 UCHAR_MAX (보통 255)까지의 각 숫자가 몇 번 나오는지 기록해뒀다가 그 횟수만큼 찍으면 된다

[밍고스사랑해(mingosudaisuki)]

이식성을 위한 포인트는 빈도 저장을 long 배열에 하고 배열 크기를 <climits>의 UCHAR_MAX를 쓰든지 <limits>의 std::numeric_limits<unsigned char>::max()를 쓰든지 해서 잡아야 한다는 두 가지뿐임

[밍고스사랑해(mingosudaisuki)]

아 물론 <climits>의 CHAR_BIT를 가지고 (1 << CHAR_BIT) - 1 해도 된다만

[밍고스사랑해(mingosudaisuki)]

생각해 보니 <<랑 -를 섞어 쓰면 뭔가 잘 안 어울리는 것 같아. CHAR_BIT를 쓰고 싶다면 ~(-1 << CHAR_BIT)로 하자.

[익명(182.211)]

거에요->거예요 [리듬 맞춤법 봇♬]

[익명(182.211)]

mozzart//갯수->개수 [리듬 맞춤법 봇♬]