Question

We're learning about quickSort. The book provides the code at the end of my question.

I'm curious about this call at the end of the findPivot method:

swap(array, left++, right--);

Why have the "++" and "--" in there? It's not incrementing/decrementing either variable (before or after the swap) and it's not accessing (for example) array[left + 1].

So what gives?

EDIT

So before I posted the question I wrote the following test code:

public static void main(String[] args) {

    int a = 0;
    int b = 2;
    int[] array = {1,10,20,30};

    swap(array, a++,b--);

}

public static void swap(int[]array,int a, int b) 
{
    for(int i = 0; i < 10; i++)
    {
    Integer temp = array[a];
   array[a] = array[b];
   array[b] = temp;

    System.out.println("a = " + a + "\nb = " + b + "\narray a: " + array[a] + "\narray b: " + array[b]);
    }

The results are as follows:

a = 0 b = 2 array a: 20 array b: 1 a = 0 b = 2 array a: 1 array b: 20 a = 0 b = 2 array a: 20 array b: 1

The variable isn't post-incrementing at all when used in the method. That's why I asked the question.

Thanks. Here's the code:

private static void swap(Integer[] array, int i, int j)
{

   Integer temp = array[i];
   array[i] = array[j];
   array[j] = temp;

}

public static void quickSort(Integer[] array, int left, int right)
{
    if(left < right)
    {
        int pivot = findPivot(array, left, right);
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }
}//quickSort

public static int findPivot(Integer[] array, int left, int right)
{
    int first = left++;
    while (left <= right)
    {
        while (left <= right && array[first].compareTo(array[left]) > 0)
        {
            left++;
        }
        while (left <= right && array[first].compareTo(array[right]) < 0)
        {
            right--;
        }
        if (left < right)
            swap(array, left++, right--);
    }
    swap(array, first, right);
    return right;
}
Was it helpful?

Solution

It are post-increment (§15.14.2) (++) and post-decrement (§15.14.3) (--) operations. These will change the values for the next iteration in your while loop.

You basically have this:

while (left <= right)
{
    // ...
    if (left < right)
    {
        swap(array, left, right);
        left++;
        right--;
    }
}

As you can see, the "post" means that the values are not affected for that particular statement. After evaluating the post increment operation, it will the variable will be increased, but the value passed to the method was still the old one. For the advanced readers, you could write the post-increment operator like this (pseudo code):

public int operator this++()
{
    int temp = this;
    ++this; // regular pre-increment (JLS §15.15.1)
    return temp;
}

For a read about the pre-increment operator, you can check JLS §15.15.1.

OTHER TIPS

swap(array, left++, right--); is inside of a while loop, so the updated values will be used in the next loop iteration.

java increment(++) and decrement(--) lets suppose i++; this means i+1 and i-- means i-1 in programming

int i = 1;
System.out.println("i : "+(i++)); // this means first print then add `1` into i;
//and
System.out.println("i : "+(++i)); // this means first add one and then print it;
// same for '--' 

They are the post increment (++) and post decrement (--) operation, so they will change the values in the next iteration in your while loop

In your code at this line

   swap(array, left++, right--);//left++ , right-- are post increment (++) and post decrement (--) operation
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top