#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int N = 20;
// DL - elementy mniejsze od elementu zwrotnego
// DP - elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego
int Dziel_na_partycje(int *D, int ip, int ik)
{ int i, pv, x;
pv = D[ip]; i = ip; ik++;
while(i < ik)
{ while(D[++i] < pv) ;
while(D[--ik] > pv) ;
if(i < ik)
{ x=D[i]; D[i]=D[ik]; D[ik]=x; }
}
D[ip] = D[ik]; D[ik] = pv;
return ik;
}
// Szybkie wyszukiwanie
int main()
{ int D[N + 1],i, ip, ik, k, piv;
srand( time(NULL));
// Losowanie danych do tablicy D
for(i=0;i < N; i++) D[i]=rand()% 1000;
D[N] = 1000; //// Na końcu D[] umieszczamy wartownika
// Wyświetlenie D[] przed podziałem
for(i=0; i < N;i++)
cout << setw(4)<< D[i];
cout << endl;
// Losowanie k
k = 1 + (rand() % 20);
// Szukamy k-tego największego elementu
ip = 0; ik =N -1;
while(true) {
piv = Dziel_na_partycje(D,ip,ik);
if(piv == N - k) break;
else if(N - k < piv) ik = piv - 1;
else ip = piv + 1;
}
// Wyświetlamy k i D[N-k]
cout << "k = " << k
<< ", k-ty najwiekszy element = " << D[N-k]
<< endl << endl;
// Wyświetlanie D[] po podziale
for(i = 0; i < N; i++) cout << setw(4) << D[i];
return 0;
}
/*
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int N = 40;
int main( )
{
int D[N], M[11], i, j, k, x;
srand (time ( NULL ) );
// Inicjujemy tablicę D[ ]
for( i = 0; i < N; i++ ) D[i] =rand()% 100;
// Losujemy k
k = 4 + rand()% 7 ;
// Ustawiamy tablicę M
for( i = 0; i < k; i++ ) M[i] = -1;
M [k] = 100;
// Szukamy k-tego największego elementu
for( i = 0; i < N; i++ )
{
x = D[i];
for( j = -1; x > M [j+1]; )// wyszukaj miejsce dla x
{
j++; M[j] = M[j+1]; //kopiowanie z przesuwaniem
}
if( j >=0 ) M[j]=x; //j wskazuj miejsce docelowe wstawienia x
}
// Wypisujemy zawartość tablicy D[]
for( i = 0; i < N; i++ )
if(D[i]==M[0])
    cout << setw(2) << ">" << D[i];
else
    cout << setw(4) << D[i];
cout << endl << endl;
// Wypisujemy zawartość tablicy M
for( i = 0; i < N; i++ ){
if(D[i]==M[0])
    cout << "Pozycja k-tego elementu: "<< i+1<< endl;
}
cout << endl;
cout << "k = " << k << ": ";
for( i = 0; i < k; i++ ) cout << setw (4) << M[i];
cout << endl << endl;
return 0;
}

5.1
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int N = 40 ;
int main()
{
int D[N], i, j, k, x, minD, poz;
srand (time ( NULL ) );
// Losujemu dane do tablicy D[]
for( i = 0; i < N; i++ ) D[i]=rand()% 100 ;
// Losujemy k
k = ( rand() % 10 ) + 1;
// Wyświetla zawartość tablicy D
for( i = 0; i < N; i++ ) cout << setw(4) << D[i];
cout << endl << endl;
// Sortowanie D [ ] przez Wybór
for( i=0; i < N-1; i++ )
{
minD = D[i];
poz = i;
for( j=i + 1; j < N; j++ )
if( D[j] < minD )
{
minD = D[j]; poz = j;
}
x=D[i]; D[i]=D[poz]; D[poz]=x;
}
// Wyświetla zawartość D[]
for( i = 0; i <N; i++ )
    if(i==N-k){
    cout << setw(2)<<">"<<D[i];
    }
    else
    cout << setw (4) <<D[i];
    cout<< endl;
cout << endl << endl;

// Wyświetla k oraz D[N-k]
cout << k << ": " << D[ N - k ] << endl << endl;
return 0;
}
*/