Cod sursa(job #2529160)

Utilizator Tudor06MusatTudor Tudor06 Data 22 ianuarie 2020 23:50:00
Problema Statistici de ordine Scor 90
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define NMAX 3000000

int v[NMAX];

void quickSelect( int k, int st, int dr ) {
  int i, pozpiv, aux;
  while ( st < dr ) {
    aux = v[st];
    v[st] = v[st + 1];
    v[st + 1] = aux;
    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;
  }
}

FILE *fin, *fout;

char buf[10000];
int ix = 10000;

char chr() {
    if ( ix == 10000 ) {
        ix = 0;
        fread( buf, 1, 10000, fin );
    }
    ix ++;
    return buf[ix - 1];
}

int numar() {
    char ch;
    int nr = 0;
    while ( isspace( ch = chr() ) );
    do {
        nr = nr * 10 + ch - '0';
    } while ( isdigit( ch = chr() ) );
    return nr;
}
int main() {
  fin = fopen( "sdo.in", "r" );
  fout = fopen( "sdo.out", "w" );
  int n, k, i;
  n = numar();
  k = numar();
  for ( i = 0; i < n; i ++ ) {
        v[i] = numar();
  }
  quickSelect( k - 1, 0, n - 1 );
  fprintf( fout, "%d", v[k - 1] );
  fclose( fin );
  fclose( fout );
  return 0;
}