Results 1 to 2 of 2
 08082016, 09:08 PM #1Senior 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.
Notes about the code:
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=j1 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; } }
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; 08092016 at 02:22 AM. Reason: added item 4 of notes
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 08092016, 05:27 PM #2Senior 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,
JimLast edited by jim829; 08102016 at 12:25 AM.
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
Similar Threads

Spring Partition framework  help needed
By ant_ony10 in forum SpringReplies: 0Last Post: 06122014, 03:22 PM 
Algorithm problem.
By luisx86 in forum New To JavaReplies: 2Last Post: 03252013, 01:43 AM 
Algorithm Problem
By Aggy in forum New To JavaReplies: 4Last Post: 01212010, 11:00 PM 
Problem with algorithm
By Albert in forum AWT / SwingReplies: 1Last Post: 07132007, 03:31 PM
Bookmarks