3-way random quicksort partition function

Question

I am trying to implement 3-way random quicksort algorithm and I am struggling to figure out what "Partition function should look like". Can someone help me implement it? The code I have written so far:

void randomized_quick_sort(vector<int> &a, int l, int r, int pivot) {
  if (l >= r) {
    return;
  }

  int k = l + rand() % (r - l + 1); // Pivot - random number between l and r
  swap(a[l], a[k]); // Swap leftmost element and pivot element

  int m1 = l;
  int m2 = r;

  partition3(a,l,r,m1,m2,k)

  randomized_quick_sort(a, l, m1 - 1);
  randomized_quick_sort(a, m2 + 1, r);
}

I need to figure out partition3() function.

Answer 1

Even though you don't show too much work done in figuring out the question or the answer here is my answer. The main idea of the function is to divide the parts into 3 ways (as the name suggests) so that an array such as 4 9 4 4 1 9 4 4 9 4 4 1 4 if 4 will be used as the pivot element it will be split into three parts; 1 1 as first, 4 4 4 4 4 4 4 4 as middle and 9 9 9 as third part and we will not take the extra 4's into further recursion thanks to this. Below is a simple implementation of it. Here I am returning the respective locations of the divided array with another array. You can easily do this by giving these locations to the function as parameters given by reference.

vector<int> partition3(vector<int> &a, int beg, int end){
  int x = a[beg];
  vector<int> ex(2);
  for(int i=beg; i<=end;){
    if(a[i]<x){
      swap(a[beg],a[i]);
      beg++;i++;
    }else if(a[i]==x){
      i++;
    }else{
      swap(a[i],a[end]);
      end--;
    }
    ex[0]=beg;ex[1]=end;
  }
  return ex;
}

If you want to read further there is a topic about it in GeeksforGeeks website with another example and more explanation. But first try to understand the answer instead of copying any other answer directly. It is fairly a simple method. Good luck!