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

#define MAX 1000
#define TAM_GRUPO 5

/* esse algoritmo devolve o k-ésimo elemento de v[p..q] */

void constroi_vetor_das_medianas(int v[], int p, int q, int vaux[], int *m) {
  int aux, i, j, ini = p, fim; 

  *m = 0;
  while (ini <= q) {
    fim = ini + TAM_GRUPO - 1; 
    if (fim > q) fim = q;
    for (i=fim; i>ini; i--) 
      for (j=ini; j<i; j++)
	if (v[j] > v[j+1]) {
	  aux = v[j];
	  v[j] = v[j+1];
	  v[j+1] = aux;
	}
    vaux[*m] = v[(ini+fim)/2];
    (*m)++;
    ini = fim + 1;
  }
}

int particiona (int v[], int p, int r) {
  int aux, x = v[p], i = p-1, j = r+1;

  while (i < j) {
    do { j--; } while (v[j] > x); 
    do { i++; } while (v[i] < x); 
    if (i < j) {
      aux = v[i]; 
      v[i] = v[j]; 
      v[j] = aux;
    }
  }
  return j;
}

int seleciona_linear (int v[], int p, int q, int k) {
  int x, i, m, vaux[MAX];

  if (p == q) 
    return v[p];
  else {
    constroi_vetor_das_medianas(v, p, q, vaux, &m);
    x = seleciona_linear(vaux, 0, m-1, m/2);
    for (i=p; i<=q; i++) 
      if (v[i] == x) v[i] = v[p];
    v[p] = x;
    i = particiona(v, p, q);               
    if (k <= i-p+1)
      return seleciona_linear(v, p, i, k);
    else 
      return seleciona_linear(v, i+1, q, k-(i-p+1));
  }
}

void embaralha (int v[], int n) {
  int r, aux;
  
  while (n > 0) {
    n--; 
    r = (int) (n * ((double)rand())/(RAND_MAX+1));
    aux = v[r]; 
    v[r] = v[n]; 
    v[n] = aux;
  }
}

int main() {
  int n, k, i, v[MAX]; 

  srand(11173); 
  
  printf("Digite n: ");
  scanf("%d", &n); 

  for (i=0; i<n; i++) v[i] = i+1;
  embaralha(v, n);

  printf("Digite k: ");
  scanf("%d", &k); 

  printf("O %d-ésimo elemento é %d.\n", k, seleciona_linear(v, 0, n-1, k));
  return 0;
}