Three Way Partitioning QuickSort

Three Way Partitioning QuickSort

  June 17, 2018    

---

In general , we pick an element as pivot and peform partitioning .
Now as per 3 way partitioning we will choose a range to perform partition.

Problem:
https://practice.geeksforgeeks.org/problems/three-way-partitioning/1

Here we are not bothered about the sequence we only care about left element should be less than range and right elements greater than .

So we choose two pointers 
1:start to replace less element
2: end to replace greater element

But we are not incrementing i every time as we  don't know that after swap element is at right position or not as if we swap larger element with last positioned end ,it might happen that that element can be less or greater then again recheck need to be done..

Code:


public ArrayList<Integer> threeWayPartition(ArrayList<Integer> a, int x, int y)
{
        int l=0,r=a.size()-1;
        int i=0;
        while(i<=r)
        {
            if(a.get(i)<x)
            {
                int temp=a.get(l);
                a.set(l,a.get(i));
                a.set(i,temp);
                ++l;
                ++i;
            }
            else if(a.get(i)>y)
            {
                 int temp=a.get(r);
                a.set(r,a.get(i));
                a.set(i,temp);
                --r;
            }
            else
            ++i;
          //  System.out.println(a);    
        }
       // System.out.println(a);
        return a;
        }