# K largest elements in an array

I solve problems to prepare for interviews. Now I have written the algorithm of finding K largest numbers in array. Various solutions are described here: https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/. Initially, I came up with the solution myself and looks my solution corresponds to that described as Method 2 on the site, with the difference that I additionally use the "old minimum" to cut off unnecessary steps along the nested loop.

What could be written better in my code? What could be used instead of pmin?

Here is my implementation:

using namespace std;

vector<int> largest_part_of_vector(const vector<int>& vec, int K_PartSize)
{
assert(K_PartSize < vec.size());

vector<int> ret(K_PartSize);

// Initial filling of temporary vector
int ind = 0; // main end-to-end index
int* pmin = const_cast<int*>(&vec[0]); // current minimum
// How pmin could be declared and used better?

for (auto& elemRef : ret)
{
elemRef = vec[ind];

if (elemRef < *pmin)
{
pmin = &elemRef; // pmin is from vecPart now and will not modify vec
}

ind++;
}

// the rest part
auto oldMin = *pmin;
for (; ind < vec.size(); ind++)
{
auto v = vec[ind];

if (v > oldMin) // preliminary check to avoid unnecessary checks
{
for (auto& elemRef : ret)
{
if (elemRef < *pmin)
{
pmin = &elemRef;
}
}

if (v > * pmin)
{
oldMin = *pmin;
*pmin = v;
}
}
/*else
{
savedIterations++;
}*/
}

return ret; // As I understand, moving operator=( vector&& other ) will be used here
}

• Of course, the real answer to such an interview question is to just call std::partial_sort_copy. Oct 27, 2021 at 14:23

using namespace std; is poor practice - don't do that.

K_PartSize should probably be a std::size_t.

assert() is not a good way to validate arguments - it's intended for making claims about invariants in the logic. It won't be present in non-debug builds, and when it is present, it can abort the program, without running destructors or any other cleanup.

if (!partsize) {
return {};
}
if (partsize >= vec.size()) {
return vec;
}


I dislike the const_cast for pmin. I think it would be better to construct ret from the beginning part of the input vector, and start pmin pointing to the first element of that:

std::vector<int> ret(vec.begin(), vec.begin()+partsize);
int* pmin = &ret[0];


I'd suggest that this would be better as an iterator than a pointer:

auto pmin = ret.begin();


I'd swap round the test of (v > oldMin):

if (v <= oldMin) {
continue;
}
for (auto& elemRef : ret)


I don't think we need both pmin and oldMin, certainly if we use the standard min_element algorithm:

#include <algorithm>
#include <vector>

std::vector<int> largest_part_of_vector(const std::vector<int>& vec, std::size_t partsize)
{
if (!partsize) {
return {};
}
if (partsize >= vec.size()) {
return vec;
}

std::vector<int> ret(vec.begin(), vec.begin()+partsize);
auto pmin = std::min_element(ret.begin(), ret.end());

// the rest part
for (auto ind = vec.begin() + ret.size();  ind != vec.end();  ++ind)
{
auto const v = *ind;

if (v <= *pmin) { continue; }

*pmin = v;
pmin = std::min_element(ret.begin(), ret.end());
}

return ret;
}


Test program:

#include <iostream>

template<typename V>
class printable_vector
{
V const& v;
public:
explicit printable_vector(const V& v) : v{v} {}
friend std::ostream& operator<<(std::ostream& os, const printable_vector& p) {
os << '{';
char const* sep = "";
for (auto const& e: p.v) {
os << sep << e;
sep = ", ";
}
return os << '}';
}
};

int main()
{
auto const a = std::vector{ 1, 2, 12, 3, 2, 6 };

for (auto k: {0, 1, 4, 5, 9}) {
std::cout << printable_vector{largest_part_of_vector(a, k)} << '\n';
}
}