Cod sursa(job #2529154)

Utilizator Tudor06MusatTudor Tudor06 Data 22 ianuarie 2020 23:37:49
Problema Statistici de ordine Scor 50
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 1000000

int v[NMAX];

void quickSelect( int k, int st, int dr ) {
  int i, pozpiv, aux;
  while ( st < dr ) {
    pozpiv = st; /// Pozitia pivotului este egala cu st
    i = st + 1; /// Incepem de la st + 1
    while ( i <= dr ) {
      if ( v[i] <= v[pozpiv] ) { /// Daca elementul este mai mic sau egal decat pivotul
        aux = v[pozpiv + 1]; /// Interschimbam pivotul cu urmatorul element
        v[pozpiv + 1] = v[pozpiv];
        v[pozpiv] = aux;
        pozpiv ++;
        if ( v[pozpiv - 1] > v[pozpiv] ) { /// Daca elementul interschimbat anterior nu este chiar elementul mai mic
          aux = v[pozpiv - 1]; /// Il interschimbam cu elemntul interschimbat anterior
          v[pozpiv - 1] = v[i]; /// cu pivotul
          v[i] = aux;
        }
      }
      i ++;
    }
    if ( k > pozpiv )
	  if ( pozpiv + 1 == st )
      	st = pozpiv;
	  else
	  	st = pozpiv + 1;
    else
	  if ( pozpiv == dr )
	  	dr = pozpiv - 1;
	  else
		dr = pozpiv;
  }
}

int main() {
  FILE *fin = fopen( "sdo.in", "r" ), *fout = fopen( "sdo.out", "w" );
  int n, k, i;
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i ++ ) {
    fscanf( fin, "%d", &v[i] );
  }
  quickSelect( k - 1, 0, n - 1 );
  fprintf( fout, "%d", v[k - 1] );
  fclose( fin );
  fclose( fout );
  return 0;
}