No Name QA
No Name QA

Reputation: 784

Quick sort Hoare array partitioning

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");?

Upvotes: 0

Views: 417

Answers (1)

xs0
xs0

Reputation: 2897

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.

Upvotes: 2

Related Questions