Find the K element of an unsorted array as if it's sorted - Divide and conquer

Question

I have a question regarding the implementation of an algorithm using Divide and conquer.

So, we have an unsorted array V[] and we have to find the k element of the array as if the array is sorted but without completely sort the array v.

Example:

Size of array = 8; k = 3; For example, if k = 3 and v = {2, 7, 5, 9, 8, 10, 3, 4} the k element of that array is 5.

Obs: The array is indexed from 0 to size - 1.

My code:

void read_STL(std::vector<int>& vect,int &k)
{
   std::ifstream fisier("file.txt");
   int dim;
   fisier >> dim;
   fisier >> k;
   for (int i = 0; i < dim; i++)
   {
      int elem;
      fisier >> elem;
      vect.push_back(elem);
   }
   fisier.close();
}

bool criteriu(int i, int j)
{
   return (i < j);
}

int search_DQ(std::vector<int>& vect, int st, int dr,int k)
{
   if (st == dr) 
   {
      return vect[st];
   }
   int mijl = (st + dr) / 2;
   if (k == mijl) 
   {
      return vect[k];
   }
   else if (k < mijl) 
   {
      return search_DI(vect, st, mijl - 1, k);
   }
   else 
   {
      return search_DQ(vect, mijl + 1, dr, k);
   }
}

int main()
{
   std::vector<int>vect;
   int st, dr, k;
   read_STL(vect,k);
   st = 0;  dr = vect.size() - 1;
   std::cout<<search_DQ(vect, st, dr,k);
   return 0;
}

Is using [`std::nth_element()`](https://en.cppreference.com/w/cpp/algorithm/nth_element) cheating? — Shawn, Nov 30 '19 at 20:25
https://stackoverflow.com/q/5011177/1918193 https://stackoverflow.com/q/251781/1918193 etc — Marc Glisse, Nov 30 '19 at 20:30
@AndyG The problem is not about finding the k-th smallest element in the array I'm afraid — GiNec, Nov 30 '19 at 20:31
@AndyG Do you have a working implementation of this algorithm that works on my example too? — GiNec, Nov 30 '19 at 20:43
@GiNec: If you make an attempt I will gladly help guide your code towards the correct solution, but I am not inclined to write the code from scratch. — AndyG, Nov 30 '19 at 20:55
@AndyG I succesfully wrote a code that finds my k-th element from the array but not as if it's sorted. Here is the code, if it helps ;) — GiNec, Nov 30 '19 at 21:27
@GiNec: Your code doesn't compile as is (`search_DI` should be `search_DQ`). After fixing that one typo, it seems to find the kth largest like you want. It's hard to tell what you're looking to get here, because you haven't actually asked a question :-) — AndyG, Dec 01 '19 at 14:26

Find the K element of an unsorted array as if it's sorted - Divide and conquer

0 Answers0