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

void swap(int *a, int *b); //두 배열의 원소를 교환하는 함수
int linear_select(int a[], int p, int r, int i);
int partition(int a[], int p, int r); //분할 함수
int select(int a[], int p, int r, int i); //기본 select 함수
int partition_bymedian(int a[], int p, int r, int middle); //middle을 기준으로 전체 원소를 분할하는 함수

int main(){
    int n=33,i=0;
    int arr[33]={1,2,55,41,69,85,32,68,20,7,45,54,86,99,102,31,22,77,44,50,52,89,61,37,6,9,78,46,28,23,94,56,11};
    scanf("%d",&i);//몇 번째 작은 원소 인지 설정
 
    int p=0,r=n-1;//p는 첫번째 인덱스, r은 마지막 원소의 인덱스

    int result = linear_select(arr,p,r,i);//선택 함수 호출
    printf("%d\n",result);
    system("PAUSE");
    return 0;
}   

int linear_select(int a[], int p, int r, int i){
    int num=(r-p+1);//정렬할 원소수
    printf("정렬할 원소들 :");
    for(int j=p; j<=r;j++)
        printf("%d ",a[j]);          
    printf("\n");
   
    /**** 단계1 ****/
    if(num<=5) // 전체 원소의 개수가 5개 이하이면 일반 선택 알고리즘 사용
       return select(a,p,r,i);

    /**** 단계2 ****/   
    int t = (int)ceil((double)num/5); //소수첫째자리에서 올림해줌
    int *b=(int*)malloc(sizeof(int)*t);//중간값을 저장할 배열 b를 n/5만큼 크기 할당
    printf("B배열의 원소 수 : %d\n",t);
   
    /**** 단계3 ****/
    int mok=num/5;//몫 구하기
    int first_index=(mok*5);//마지막 그룹의 첫번재 인덱스
 int index=0;
    for(int start=p; start<(first_index); start=start+5){
       b[index++]=select(a,start,start+4,3);
    }
   
 int rest = r-first_index+1; //맨 마지막 그룹의 원소의 개수는 몇개인가?
    if(rest>0){   
        if(rest==5){ //5개일때는 
           b[t-1]=select(a,first_index,first_index+4,3);        
        }else if(rest==4){
           b[t-1] = select(a,first_index,first_index+3,2); //4개일때는 2번째 원소를 중앙값으로
        }else if(rest==2){
           b[t-1] = select(a,first_index,first_index+1,1); //2개일때는 첫번째 원소를 중앙값으로
        }else{
        int center =int((double)(rest)/2+0.5);
        b[t-1] = select(a,first_index,first_index+rest-1,center); //홀수 1,3이면 중앙값 1,2번째 원소를 중앙값으로
        }
 }

   
    printf("중간값 들:");
    for(int j=0; j<t;j++)
        printf("%d ",b[j]);          
    printf("\n");
   
    /**** 단계4 ****/
    int middle=linear_select( b,0,t-1,(int)ceil((double)t/2) );//중간값들에 대해서 다시 중간값을 찾는다.
 printf("중 간 값 : %d\n",middle); //중간값 출력
   
    /**** 단계5 ****/
    int q = partition_bymedian(a, p, r, middle); //middle을 기준원소로 삼아 전체 원소를 분할
    //q는 중간값의 인덱스이다.
   
    /*
    for(int j=p; j<=(r-p);j++)
        printf("%d ",a[j]);          
    printf("\n");*/
   
    printf("재배열된 원소들 :");
    for(int j=p; j<=r;j++)
        printf("%d ",a[j]);          
    printf("\n");
    printf("i:%d ,q:%d\n",i,q);
   
    printf("\n");
    printf("\n");
   
    /**** 단계6 ****/
    if(i==q){
     return a[q]; 
    }else if(i<q){
  return linear_select(a,p,q-1,i);
    }else{
  return linear_select(a,q+1,r,i-q+p-1);
    }
}
 
//중앙값을 기준으로 전체 원소 분할
int partition_bymedian(int a[], int p, int r,int middle){
    printf("교환 전 원소 들:");
    for(int j=p; j<=r;j++)
        printf("%d ",a[j]);          
    printf("\n");
    int index=0;
    for(int i=p;i<=r;i++){
        if(a[i]==middle)
           index=i; //middle의 인덱스를 찾아서 반환
    }
    swap(&a[index],&a[r]);
    printf("교환 후 원소 들:");
    for(int j=p; j<=r;j++)
        printf("%d ",a[j]);          
    printf("\n");
    return partition(a,p,r);                   
}

int select(int a[], int p, int r, int i){ //기본 선택함수
    if(p==r)
       return a[p];
    else{ 
       int q = partition(a,p,r);
       int k = q-p+1;
       if(i<k)
          return select(a,p,q-1,i);
       else if(i==k)
          return a[q];
       else
          return select(a,q+1, r, i-k);
    }
} 

int partition(int a[], int p, int r){ //분할 하는 함수
    int x=a[r]; //기준원소 
    int i=p-1;
    for(int j=p; j<=r-1; j++){
        if(a[j]<=x){
           i++;
           swap(&a[i],&a[j]);
        }
    }
    swap(&a[i+1],&a[r]);
   
    return (i+1);                    
}

//두 원소 교환하는 swap함수
void swap(int *a, int *b){
  int t = *a;
  *a = *b;
  *b = t;
}


근데 왜 교수님이 테스트하는 컴파일러에서는 안돌아가냐