Results 1 to 2 of 2
  1. #1
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default 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

    Problem with Hoare's partition algorithm-hoares_partition.jpg
    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!
    -----------------------------------------
    Attached Files Attached Files
    Last edited by jim829; 08-09-2016 at 02:22 AM. Reason: added item 4 of notes
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

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

    Default 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.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. Spring Partition framework - help needed
    By ant_ony10 in forum Spring
    Replies: 0
    Last Post: 06-12-2014, 03:22 PM
  2. Algorithm problem.
    By luisx86 in forum New To Java
    Replies: 2
    Last Post: 03-25-2013, 01:43 AM
  3. Algorithm Problem
    By Aggy in forum New To Java
    Replies: 4
    Last Post: 01-21-2010, 11:00 PM
  4. Problem with algorithm
    By Albert in forum AWT / Swing
    Replies: 1
    Last Post: 07-13-2007, 03:31 PM

Posting Permissions

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