Quick Sort partition function

Question

I would like to ask a question for quick sort partition function(). If I replace the statement

int pivot = arr[(left + right) / 2];

with

int pivot = arr[left+(right-left)>>1];

The algorithm does not work when there is duplicated elements in the array. Why? Thanks.

int partition(int arr[], int left, int right) 

{ 

      int i = left, j = right; 

      int tmp; 

      int pivot = arr[(left + right) / 2]; **********        

      while (i <= j) { 

            while (arr[i] < pivot)  i++; 
            while (arr[j] > pivot)  j--; 

            if (i <= j) { 
                  tmp = arr[i]; 
                  arr[i] = arr[j];
                  arr[j] = tmp; 
                  i++; 
                  j--; 
            } 
      }     

      return i; 
}

Obicere · Accepted Answer · 2014-03-16 01:54:40Z

2

The problem is the precedence of the operators.

The order for the 3 you use is as follows:

Multiplicative
Additive
Shift

What happens, is that left+(right-left)>>1 is treated as if it were (left+(right-left))>>1, which is not equal, but rather just right >> 1 or right / 2.

You can see precedence here: http://docs.oracle.com/javase/tutorial/java/nutsandbolts/operators.html

answered Mar 16, 2014 at 1:54

Obicere

3,0193 gold badges22 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

susanna Over a year ago

Thank you! I get it! precedence problem!

Niklas B. Over a year ago

Happens to the best of us

TheMorph · Accepted Answer · 2014-03-16 01:57:22Z

0

With

int pivot = arr[left+(right-left)>>1];

You are actually writing

int pivot = arr[(left+(right-left))/2];

Which is equal to

int pivot = arr[right/2];

So you are selecting a different pivot element than in your first code. Nevertheless quick sort should return the right solution as long as the pivot element you chose is within the bounds of the current sub-array. With your modification you will eventually select an pivot element that is not in your current sub-array.

answered Mar 16, 2014 at 1:57

TheMorph

5722 silver badges10 bronze badges

2 Comments

susanna Over a year ago

Thank you! I get it! It is the precedence problem!

TheMorph Over a year ago

As Niklas B. wrote: Happens to anyone. ;)

Collectives™ on Stack Overflow

Quick Sort partition function

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related