Pagini recente » Cod sursa (job #924444) | Cod sursa (job #858294) | Cod sursa (job #2065201) | Cod sursa (job #501153) | Cod sursa (job #2462527)
#include <fstream>
#include <vector>
constexpr int countsize = 256;
constexpr int bucketsize = 8;
constexpr int mask = (1 << bucketsize) - 1;
int computeIndex(int val, int bucket)
{
return val >> (bucket * bucketsize) & mask;
}
std::vector<int> computeFrequencies(const std::vector<int>& input, int bucket)
{
std::vector<int> frequence(countsize, 0);
for (auto it = input.cbegin(); it != input.cend(); ++it)
{
auto c = computeIndex(*it, bucket);
frequence[c]++;
}
return frequence;
}
std::vector<int> computePositions(const std::vector<int>& frequence)
{
std::vector<int> index(countsize, 0);
int i, count = frequence[0];
for (i = 1; i < countsize; i++)
{
if (frequence[i])
{
index[i] = count;
count += frequence[i];
}
}
return index;
}
std::vector<int> moveElements(const std::vector<int>& input, std::vector<int>& frequence, std::vector<int>& index, int bucket)
{
std::vector<int> temp(input.size(), 0);
for (auto it = input.cbegin(); it != input.cend(); ++it)
{
auto pos = computeIndex(*it, bucket);
frequence[pos] --;
temp[index[pos]] = *it;
index[pos]++;
}
return temp;
}
void radixSort(std::vector<int>& input)
{
for (auto bucket = 0; bucket < 4; bucket++)
{
auto frequence = computeFrequencies(input, bucket);
auto index = computePositions(frequence);
input = moveElements(input, frequence, index, bucket);
}
}
int main()
{
std::ifstream fin("sdo.in");
std::ofstream fout("sdo.out");
int n=0, k=0, i=0, x=0;
fin>>n>>k;
std::vector<int> v;
for(i=0; i<n ; ++i){
fin>>x;
v.push_back(x);
}
radixSort(v);
fout<<v[k-1];
return 0;
}