Cod sursa(job #2041461)

Utilizator dementorrDementhor dementorr Data 17 octombrie 2017 12:48:28
Problema Statistici de ordine Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>

int v[3000000];

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

void sdo(int left, int right, int k) {
  if (left >= right)
    return;
  
  int piv = v[(left + right) / 2], begin = left, end = right;
  
  while (begin <= end) {
    while (v[begin] < piv)
      ++begin;
    while (v[end] > piv)
      --end;
  
    if (begin <= end) {
      swap(&v[begin], &v[end]);
      ++begin;
      --end;
    }
  }
  
  if (k <= end)
    sdo (left, end, k);
  else
    sdo (begin, right, k);
}

void quicksort(int *v, int left, int right) {
  int pivot = v[(left + right) / 2];

  if (left >= right)
    return;
  
  int begin = left, end = right;
  while (begin <= end) {    
    while (v[begin] < pivot)
      ++begin;
    while (v[end] > pivot)
      --end;

    if (begin <= end) {
      swap (&v[begin], &v[end]);
      ++begin;
      --end;
    }
  }

  quicksort (v, left, end);
  quicksort (v, begin, right);
}

int main () {

  freopen ("sdo.in", "r", stdin);
  freopen ("sdo.out", "w", stdout);
  

  int n, k;
  scanf ("%d%d", &n, &k);

  int i;
  for (i = 0; i < n; ++i)
    scanf ("%d", &v[i]);

  sdo (0, n - 1, k);
  printf ("%d\n", v[k - 1]);
  
  return 0;
}