Cod sursa(job #1109897)

Utilizator vladradu2014Radu Vlad Alexandru vladradu2014 Data 17 februarie 2014 18:08:40
Problema Statistici de ordine Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <malloc.h>
#include <string.h>

void swap(int *V,int i,int j){
 int aux=V[i];
 V[i]=V[j];
 V[j]=aux;
}

int kthmin(int *V,int K,int start,int end){
    int med=start+(end-start)/2;
    int i=start;
    int j=end;
    
    while(i<=j && i<med && j>med){
        while(V[med]>V[i]&&i<med)
          i++;
        while(V[med]<V[j]&&j>med)
          j--;
        if(i<=j){
          swap(V,i,j);
          i++;
          j--;
        }    
    }
    
    if(med==K-1)
      return V[K-1];
    else
       if(med<K)
         kthmin(V,K,med+1,end);
       else
         kthmin(V,K,start,med-1);

}



int main(){
    
   FILE *fp;
   int N;
   int K;
   int *V;
   int it;
   freopen("sdo.in","r",stdin);
   freopen("sdo.out","w",stdout);
   scanf("%d%d",&N,&K);
   V=(int*)malloc(N*sizeof(int));
   for(it=0;it<N;it++)
      scanf("%d",&V[it]);
      
  printf("%d",kthmin(V,K,0,N-1));
  return 0;
}