#77. [백준_C언어] 11004 : K번째 수 \ 정렬

 

입력 코드

#include <stdio.h>

int A[5000000];

void swap(int *a, int *b) {
	int tmp=*a;
	*a=*b;
	*b=tmp;
}

int partition(int lo, int hi) {
	int i, j, p;
	p=A[(lo+hi)/2];
	i=lo-1;
	j=hi+1;
	
	while(1){
		while(A[++i]<p);
		while(p<A[--j]);
		if(i>=j){
			break;
		}
		swap(&A[i], &A[j]);
	}
	return i;
}

int qsearch(int lo, int hi, int k) {
	int i, j, p;
	
	if (lo==hi){
		return A[lo];
	}
	
	i=lo-1;
	j=hi+1;
	p=A[(lo+hi)/2];
	while(1){
		while(A[++i]<p);
		while(p<A[--j]);
		if(i>=j){
			break;
		}
		swap(&A[i], &A[j]);
	}
    
	if(i==j && i==k){
		return p;
	}
	
	if(k<i){
		return qsearch(lo, i-1, k);
	}
	else{
		return qsearch(j+1, hi, k);
	}
}

int main() {
	int i, N, K;
	
	scanf("%d %d", &N, &K);
	
	for(i=0; i<N; i++){
		scanf("%d", A+i);
	}
	
	printf("%d\n", qsearch(0, N-1, K-1));
	
	return 0;
}

출처 www.acmicpc.net/source/21891306

 

 

코드 설명

#정렬

 

 

문제 출처

www.acmicpc.net/problem/11004

11004번: K번째 수