Hoare Partition Correctness in java

Question

I am working to implement a Hoare partition into a quicksort. I am trying to completely understand the hoare partition but the book doesnt explain everything. Mainly I am just wondering what the while TRUE part means? The excerpt from the book is below. If I were to put the while part in java what would I use and why?

Hoare-Partition(A,p,r)
    x= A[p]
    i = p-1
    j=r+1
    while true
        repeat
            j=j-1
        until A [j] <= x
        repeat
            i = i +1
        until A[i] >= x
        if i < l
           exchange A[i] with A[j]
        else return j

`while true` may mean to indicate a Infinite loop. java code: while(true) — codeMan, Feb 28 '13 at 04:32
I guess that makes sense, let me post the rest of the code that might be necessary if that is the case — shinjuo, Feb 28 '13 at 04:34
I have never messed with an infinite loop like that and have never seen it in pseudo code like that — shinjuo, Feb 28 '13 at 04:37

score 2 · Accepted Answer · answered Feb 28 '13 at 04:48

2

try this code for the algo that you have above :

int HoarePartition (int a[],int p, int r) 
{
    int x=a[p],i=p-1,j=r+1;
    while (true) 
    {
        while (a[j] <= x) j--; 
        while (a[i] >= x) i++;
        if  (i < j) swap(a[i],a[j]);
        else return j;
    }
}

answered Feb 28 '13 at 04:48

codeMan

5,730
3
27
51

1

This code is incorrect because the logic does not match the original pseudocode. The semantics of the pseudocode's `repeat ... until (condition)` should be written in Java as `while (not condition) ...`. – stackoverflowuser2010 Mar 28 '16 at 05:03

score 1 · Answer 2 · answered Jun 26 '17 at 20:22

Here's a working translation:

  public static void quicksort(int[] ar) {
    if (ar == null) return;
    quicksort(ar, 0, ar.length-1);
  }

  private static void quicksort(int[] ar, int lo, int hi) {
    if (lo < hi) {
      int splitPoint = partition(ar, lo, hi);
      quicksort(ar, lo, splitPoint);
      quicksort(ar, splitPoint+1, hi);
    }
  }

  private static int partition(int[] ar, int lo, int hi) {
    int pivot = ar[lo];
    int i = lo-1, j = hi+1;
    while(true) {
      do { i++; } while(ar[i] < pivot);
      do { j--; } while(ar[j] > pivot);
      if (i < j) swap(ar, i, j);
      else return j;
    }
  }

  private static void swap(int[] ar, int i, int j) {
    int tmp = ar[i];
    ar[i] = ar[j];
    ar[j] = tmp;
  }

Hoare Partition Correctness in java

2 Answers2

Linked