글 읽기 - 새로운 종류의 정렬방식..?

jungby1 5년 전 0

제가 힙정렬이나 병합정렬을 모를 때 그냥 작성해서 했는데 맞았는데... 혹시 이런 종류의 정렬도 어떤지 봐주실 수 있을까요 ??

그냥 숫자와 일치하는 배열의 인덱스에 저장해서 처음부터 다 출력하는 방식인데... 메모리를 좀 잡아먹는 단점이 있지만 힙정렬이나 병합정렬도

마찬가지 일 것 같고 시간복잡도도 그냥 배열에 저장하면 되니 n 정도 되지 않을까 생각합니다... 테스트 케이스가 작은 경우에는 그냥 간편하게 쓰기에는

좋을 듯 한데 어떻게 생각하는지 물어보고 싶습니다.

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

int main() {
	long N; long n;
	long i;
	scanf("%ld", &N);
	long* array = (int*)malloc(sizeof(long)*2000001);
	for (i = 0; i < 2000001; i++) {
		array[i] = 0;
	}
	for (i = 0; i < N; i++) {
		scanf("%ld", &n);
		array[n + 1000000] = n;
		if (n == 0)
			array[n + 1000000] = 1000001;
	}
	for (i = 0; i < 2000001; i++) {
		if (array[i] != 0 && array[i] != 1000001) {
			printf("%ld\n", array[i]);
		}
		else if (array[i] == 1000001)
			printf("0\n");
	}
	free(array);
	return 0;
}

bupjae 5년 전 1

이런 종류의 정렬법을 Counting Sort 라고 부릅니다.

배열에 넣을 값을 좀 더 잘 생각해 본 뒤에 10989 번 문제를 풀어보세요.

chogahui05 5년 전 2

숫자의 범위가 큰 경우에도 M진법으로 잘 쪼개면 jung님이 말한 방식으로 충분히 돌릴 수 있습니다.

쓰이는 예시

K번째 수를 구할 때 최악의 경우에도 O(n)이 보장되게 하고 싶다. 단, 들어오는 수는 [-10억,10억]이다.

(1) [-10억, 10억]을 +10억만큼 평행이동 시켜서 [0, 20억]으로 만든다.

(2) 65536 * 65536 > 20억이므로 해당 숫자를 65536*a + b로 쪼갠다.

(3) b를 기준으로 1차 정렬. b의 값이 [0,65536) 이므로, counting sort를 돌릴 수 있다.

(4) a를 기준으로 2차 정렬. 이 때 a의 값도 [0,65536)이다.

(5) sort complete!

Suffix array를 O(nlogn)에 구축하고 싶다.

내부적으로 {r1,r2}에 따라 정렬을 하는데 0<=r1<|s|이고, 0<=r2<|s|이다.

|s|는 count sort를 돌릴 만큼이므로, K번째 수를 O(n)에 구하는 트릭을 똑같이 적용하면 된다.

jungby1 5년 전 0

와 다들 좋은 의견 감사합니다!! 이게 카운팅 소트라는 거였군요 ㅋㅋ chogahui05 님 이런 방법이 있었다니... 아직 한참 배울게 남았다는 것을 느낍니다..

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

문제

문제

출처

ICPC

새로운 종류의 정렬방식..?

jungby1 5년 전 0

bupjae 5년 전 1

chogahui05 5년 전 2

jungby1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말