Partitioning an array on a Pivot

14,753

Check this implementation. It works exactly on the same principle. Try to compare and see where you are going wrong.

Note that you are supposed to swap the values of a[i] and a[j] if i <= j and also break from the loop. You are doing it on the else, which is wrong, because if a[i] is greater than the pivot and a[j] is less than the pivot by the time you reach the if, then they should be swapped if i <= j.

Share:
14,753
user2434
Author by

user2434

Updated on June 04, 2022

Comments

  • user2434
    user2434 almost 2 years

    I am trying to write a simple algorithm for moving the elements around pivot such that the elements on the left of pivot is smaller than the pivot and the element on the right of pivot is greater than it (the same step in quick sort). I have written code that works, but after that I changed the algorithm to the below, and it is not working.

    The idea of the algorithm is simple.

    Have two pointers, one at the beginning of the array and one at the end of array. If the elements pointed by i are lesser than pivot, keep skipping it until we find a greater element; and keep decrementing j until we find an element greater than the smaller element. [It is a common algorithm]

    Now the code

    private  static void sortByPivot(int[] a)
    {
    
        Random r = new Random();
        int index = r.nextInt(a.length);
        int pivot = a[index];
    
        System.out.println("pivot = " + pivot);
    
        int i =0 , j = a.length -1;
    
        while(true)
            {
    
                while(a[i] <= pivot) i++;
    
                while( j >0 && a[j] >= pivot) j--;
    
                if(i <= j)
                {
                    break;
                }
                else{
                    swap(a,i,j);
                   }
    
            }
    
            swap(a,i,index); //swap the pivot and the i
    }
    

    Swap routine :

    private static void swap(int[] a, int i , int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    

    When I run this with the following array

      int[] a = {46,3,8,4,2,6,244,76} 
    

    and when the pivot is picked as 4 the output is

             4 3 8 46 2 6 244 76 
    

    For some other pivots that are in the edge, I get a null pointer exception.

    Is there any flaw in the implementation. The logic seems right to me. I have been trying it for quite sometime but I am unable to fix it.

  • Oliver Charlesworth
    Oliver Charlesworth over 12 years
    The pivot routine is usually used as part of a sort routine. So implementing it with a sort routine somewhat defeats the point...