# Thread: Problem with Hoare's partition algorithm

1. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Problem with Hoare's partition algorithm

OK, I'm not certain which subforum this should go so please move as appropriate. I have
been reviewing sorting algorithms and have had problems getting consistent results with
C.A.R. Hoare's partition scheme. I have checked various sources online and others seem to
have similar problems (and quite often the suggested corrections don't fix the problem).
The algorithm should be simple to code. I have gone thru it by hand and get the same results
as the program below. I have included the following image of the actual algorithm and have
attached the pdf lecture slides from which it came. I would appreciate any insight as to
where the problem lies.

1. The partition schemes are the core. The other methods are simply support.
2. The r.ints(8,1,21).toArray() can be used to generate random arrays for testing.
3. I tested Lumoto's algorithm 20,000 times with random array lengths from 100 to 10000
with random values up to 1000 with no failures.
4. The output generated shows the computed pivot enclosed in parens.

Regards,
Jim

Java Code:
```import java.util.Random;

public class Partition {
public static void main(String[] args) {
Random r = new Random(21342);
int testData[][] = { { 5, 3, 2, 6, 4, 1, 3, 7 // taken from lecture,
// example 1.
}, { 5, 3, 2, 6, 5, 1, 3, 7 // taken from lecture, example 2.
}, { 5, 12, 4, 15, 10, 5, 9, 8
}, { 6, 12, 10, 3, 1, 3, 4, 2
}, // r.ints(7,1, 21).toArray(); // add this for random array
r.ints(8,1,21).toArray(), // another success!

};

for (int t = 0; t < testData.length; t++) {
int[] a = testData[t];
System.out.println("Before: " + formatString(a, 0, false));
int mid = hoare_partition(a, 0, a.length - 1);
System.out.println("After:  " + formatString(a, mid, true));

System.out.println(validate(a, mid) ? "Success!"
: "Fail!");
System.out.println("-----------------------------------------");
}
}

/**
* C.A.R. Hoare's partition algorithm
*/
public static int hoare_partition(int[] a, int p, int r) {
int pivot = a[p];
int i = p - 1;
int j = r + 1;
while (true) {
while (a[++i] < pivot); // repeat: i=i+1 until a[i] >= pivot
while (a[--j] > pivot); // repeat: j=j-1 until a[j] <= pivot

if (i >= j) {
return j;
}
swap(a, i, j);
}
}
/**
*  Lumoto's partition algorithm
*/
public static int lomuto_partition(int[] a, int p, int r) {
int pivot = a[r];
int i = p - 1;
for (int j = p; j <= r - 1; j++) {
if (a[j] <= pivot) {
swap(a, ++i, j);
}
}
swap(a, ++i, r);
return i;
}

public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static String formatString(int[] a, int mid, boolean showPivot) {
String ret = "";
for (int j = 0; j < a.length; j++) {
int v = a[j];
ret += showPivot && j == mid ? "(" + v + ")"
: (" " + v + " ");
}
return ret;

}

public static boolean validate(int[] a, int mid) {
int pivot = a[mid];
for (int j = 0; j < mid; j++) {
if (a[j] > pivot) {
return false;
}
}
for (int j = mid + 1; j < a.length; j++) {
if (a[j] < pivot) {
return false;
}
}
return true;
}

}```
Program output.

Before: 5 3 2 6 4 1 3 7
After: 3 3 2 1 (4) 6 5 7
Success!
-----------------------------------------
Before: 5 3 2 6 5 1 3 7
After: 3 3 2 1 (5) 6 5 7
Success!
-----------------------------------------
Before: 5 12 4 15 10 5 9 8
After: 5 (4) 12 15 10 5 9 8
Fail!
-----------------------------------------
Before: 6 12 10 3 1 3 4 2
After: 2 4 3 3 (1) 10 12 6
Fail!
-----------------------------------------
Before: 9 1 18 8 3 6 18 12
After: 6 1 3 (8) 18 9 18 12
Success!
-----------------------------------------
Last edited by jim829; 08-09-2016 at 02:22 AM. Reason: added item 4 of notes

2. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Problem with Hoare's partition algorithm

Eureka! I think I figure out what I was doing wrong. I made a bad assumption. I had thought that the returned value was the location of the new pivot point. It is actually the point which divides the partitions as compared to the original pivot choice. So regardless of what is returned from the partition method, the pivot is always the leftmost value in the original array. Sometimes, the pivot value and the returned index do actually match up. But this is not always the case (as was stated in the Wikipedia writeup on quicksort).

In the Lumoto algorithm, the pivot and the returned index always seem to match so the returned array looks like a properly partitioned array.

As usual if my analysis off, please let me know.

Regards,
Jim
Last edited by jim829; 08-10-2016 at 12:25 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•