Problem D : 계수정렬(counting sort)1

#include <stdio.h>
#define MAX_SIZE (1000000) // 들어오는 숫자의 개수

static int N, Q, A[MAX_SIZE]; // 들어오는 숫자의 갯수, 질의 수, 들어오는 숫자 저장 배열

extern void countingSort(int, int*); //카우팅 소트
extern int query(int); // 해당 인덱스에 들어있는 숫자를 출력

static void input() { 
	scanf("%d", &N); // 숫자 입력 받음
	for (int i = 0; i < N; ++i) {
		scanf("%d", A + i); // 배열에 입력을 받음
	}
	countingSort(N, A); // 카운팅 소트 진행
}

static void run() {
	int i, idx;
	scanf("%d", &Q); // 쿼리의 갯수를 입력 받고
	for (i = 0; i < Q; ++i) {
		scanf("%d", &idx); // 알고 싶은 인덱스를 입력 받음
		int userAns = query(idx);
		printf("%d\n", userAns); // 결과값 출력
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	input();
	run();
	return 0;
}

#define ADD 32768 // 음수를 양수로 바꾸기 위해 사용

int cs[1000001], cnt[70000]; // raw data 배열, 

void countingSort(int n, int *arr) { // 갯수, 배열 넘어옴
	int i;
	for (i = 0; i < n; i++) cnt[arr[i] + ADD]++; // 개수 세기
	for (i = 1; i < 66000; i++) cnt[i] += cnt[i - 1]; //누적 값 구하기
	for (i = n - 1; i >= 0; i--) cs[--cnt[arr[i] + ADD]] = arr[i]; // 해당 위치에 저장
}

int query(int idx) {
	return cs[idx];
}

N개의 정수를 입력받아 오름차순으로 정려라고, Q개의 질의에 응답하는 프로그램을 작성하시오. 질의는 정렬된 결과에서 idx에 위치하는 값이 무엇인지에 응답하는 것