In-place randomized selection algorithm

We are currently researching algorithms, so I have posed this question as "homework" although this is not a homework-related issue. Just to be safe.

We've just looked at a randomized selection algorithm and the logic seems simple. Select an item from the list and then place the item where you want. Then repeat the process on one additional list until the item in the index is in place. Where index is the position of the item you want in the sort list.

This should be a modified version of the quicksort algorithm. But we're only sorting one additional list, not both subscriptions. Hence, increased productivity (in big-oh).

I can successfully implement this algorithm using external stores (C ++ and zero-based arrays):

int r_select2(vector<int>& list, int i)
{
   int p = list[0];

   vector<int> left, right;

   for (int k = 1; k < list.size(); ++k)
   {
      if (list[k] < p)  left.push_back(list[k]);
      else     right.push_back(list[k]);
   }

   int j = left.size();

   if (j > i) p = r_select2(left, i);
   else if (j < i) p = r_select2(right, i - j - 1);

   return p;
}

      

        
        
        
      

    

However, I want to implement the algorithm using in-situ (in-place) rather than using additional helper arrays. I believe this should be a simple / trivial task. But somewhere my in-situ version goes wrong. Maybe its only late and I need to sleep, but I can't figure out the reason why the following version failed:

int r_select(vector<int>& list, int begin, int end, int i)
{
   i = i + begin;
   int p = list[begin];

   if (begin < end)
   {
      int j = begin;
      for (int k = begin + 1; k < end; ++k)
      {
         if (list[k] < p)
         {
            ++j;
            swap(list[j], list[k]);
         }
      }

      swap(list[begin], list[j]);

      if (j > i) p = r_select(list, begin, j, i);
      else if (j < i) p = r_select(list, j + 1, end, i - j);
   }

   return p;
}

      

        
        
        
      

    

In both examples, the first element is used as a pivot to simplify design. In both examples i

, this is the index of the element I want.

Any ideas missing the second example? Is this a simple mistake at one time?

Thanks everyone!