Help with algorithms

I was given this algorighm to write a code for a quick sort method:

To partition a[left…right] such that a[left…j–1] are all less than or
equal to a[j], and a[j+1…right] are all greater than or equal to a[j]:
1. Set pivot to a
.
2. Set i = left + 1 and j = right.
3. While i ≤ j, repeat:
3.1. While i ≤ j and a ≤ pivot, increment i.
3.2. While j ≥ i and a[j] ≥ pivot, decrement j.
3.3. If i < j, swap a and a[j].
4. If j * left, set a
to a[j], and a[j] to pivot.
5. Terminate with answer j.

And this is the code i came up with

public static int partition1(Comparable[] a, int left, int right) {

Comparable pivot = a
;
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j) {
a.compareTo(pivot);
i++;
}
while (j >= i) {
a.compareTo(pivot);
j--;
}
if (i < j) {
a = a[j];
a[j] = a;
} else if (j != left) {
a
= a[j];
a[j] = pivot;
}
}
return j;
}


The problem is that this code doesn't work. Could you help me understand what im doing wrong please!

Comments

  • Here is your code re-indented with some comments to get you started.
    The best way to check how it is working is to step through it with a debugger and see if it is doing what you think it should.
    Comparable pivot = a[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
      while (i <= j) {
        a[i].compareTo(pivot);   [COLOR="Red"]// You need to check the return value of this in your if test[/COLOR]
        i++;
      }
      while (j >= i) {
        a[i].compareTo(pivot);  [COLOR="Red"]// You need to check the return value of this in your if test, also it should be checking a[j] not a[i][/COLOR]
        j--;
      }
      if (i < j) {
        a[i] = a[j];   [COLOR="Red"]// This won't swap a[i] and a[j] as you are changing a[i] before you access it. Use a temporary object[/COLOR]
        a[j] = a[i];
      } else if (j != left) {  [COLOR="Red"]// According to your algorithm this should be after the loop[/COLOR]
        a[left] = a[j];
        a[j] = pivot;
      }
    }
    return j;
    
  • thanks mate. Works fine now. this is my code

    public static int partition(Comparable[] a, int left, int right) {

    Comparable pivot = a
    ;
    int i = left + 1;
    int j = right;
    while (i <= j) {
    while (i <= j && a.compareTo(pivot) <= 0) {
    i++;
    }
    while (j >= i && a[j].compareTo(pivot) >= 0) {
    j--;
    }

    if (i < j) {
    Comparable temp = a;
    a = a[j];
    a[j] = temp;
    }
    }
    if (j != left) {
    a
    = a[j];
    a[j] = pivot;
    numCopies +=2;
    }
    return j;
    }
  • another algorithm im working on just now

    Let p be the position in the array such that a[p] is the median
    of a
    , a[m], and a[align=right] (where m is about midway
    between left and right).

    ive got this so far

    int m = (left+right)/2;
    int p = 0;

    I am not quite following, how can you find a median from a median, or a median from 1 number?
Sign In or Register to comment.