Partitioning an array on a Pivot

问题:

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.

回答1:

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.

回答2:

If you're just trying to sort it all, (I know you said "partition" but would it be a problem if the whole thing was sorted?) there are built in methods for that

java.util.Arrays.sort(int[] a)
java.util.Arrays.sort(int[] a, int fromIndex, int toIndex)

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Arrays.html

If you're requirement is to do it yourself (homework!) then try the debugging approach above; write on paper what you expect, then step through completely to see what happens

回答3:

The logic is not correct. You have just written the code. Just take a moment and dry run this program on any input and you will directly find the flaw.

A better approach would be to take the approach depicted here on wikipedia This is the inplace version of partitioning an array used in quick sort. Hope it solves your problem.