Quick sort Hoare array partitioning

Question

Trying to figure out why Hoare partition algorithm always splits an array into two right parts. In code below, I extend Hoare algorithm to make it more clear to me (see comments for details)

int partition(int[] arr, int leftIndex, int rightIndex) {
  int pivot = arr[(leftIndex + rightIndex) / 2];

  while (leftIndex <= rightIndex) {
    while (arr[leftIndex] < pivot) leftIndex++;
    while (arr[rightIndex] > pivot) rightIndex--;

    // If all numbers at right places, than leftIndex and rightIndex 
    // could point at same array element index
    // So it's means partion done. 
    // We should return leftIndex + 1 cause 
    // rightIndex points at the last element of the left sub array

    if (leftIndex == rightIndex) return leftIndex + 1; 

    if (leftIndex < rightIndex) {
      swap(arr, leftIndex, rightIndex);
      leftIndex++;
      rightIndex--;
    }
  }

  //But here the tricky thing: Why does this "if case" never execute?
  if (leftIndex - 1 > rightIndex) 
    System.out.println("leftIndex - 1 > rightIndex");

  return leftIndex;
}

So the question is: Is it possible to pass an array to partition function, so the line below will be executed?

if (leftIndex - 1 > rightIndex) 
  System.out.println("leftIndex - 1 > rightIndex");?

xs0 · Accepted Answer · 2017-12-13 11:51:26Z

2

For that to execute, leftIndex would have to be at least rightIndex + 2, and that just can't happen, assuming we start the function with leftIndex <= rightIndex:

With these two loops:

while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;

The indices can never cross each other - if not sooner, they'll stop at either side of the pivot.

Then we leave the function if this is the case:

if (leftIndex == rightIndex) return leftIndex + 1;

So, the only thing that remains is:

if (leftIndex < rightIndex) {
  swap(arr, leftIndex, rightIndex);
  leftIndex++;
  rightIndex--;
}

Even if they're as close as can be (leftIndex == rightIndex - 1), after that executes they'll be at leftIndex == rightIndex + 1. And we still didn't get a difference of 2.

answered Dec 13, 2017 at 11:51

xs0

2,88719 silver badges25 bronze badges

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

Collectives™ on Stack Overflow

Quick sort Hoare array partitioning

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related