Quick-sort in Java using Comparable

I was asked to improve given quick-sort algorithm:

public void quickSort(Comparable[] a, int left, int right) {
// Sort a[left…right] into ascending order.
    if (left < right) {
        int p = partition(a, left, right);
        quickSort(a, left, p-1);
        quickSort(a, p+1, right);   
    }
}    




public int partition(Comparable[] a, int left, int right) {
// Partition a[left…right] such that  
// a[left…p-1] are all less than or equal to a[p] 
// and a[p+1…right] are all greater than or equal to 
// a[p]. Return p.
    Comparable pivot = a[left];
    int p = left;
    for (int r = left+1; r <= right; r++) {
        int comp = a[r].compareTo(pivot);
        if (comp < 0) {
            a[p] = a[r];  a[r] = a[p+1];
            a[p+1] = pivot;  p++;
        }
    }
    return p;
}

... using psude-code instructions below so it could work using less number of copies than initial algorithm:

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[left].
2.  Set i = left + 1 and j = right.
3.  While i <= j, repeat:
    3.1.    While i <= j and a[i] <= pivot, increment i. 
    3.2.    While j >= i and a[j] >= pivot, decrement j.
    3.3开发者_运维技巧.    If i < j, swap a[i] and a[j].
4.  If j != left, set a[left] to a[j], and a[j] to pivot. 
5.  Terminate with answer j.

The problem is I cannot sort out this bit:

While i <= j and a[i] <= pivot,

as I'm getting error message saying I can't use < and > signs with Comparable. I've found few solutions online but none of them worked.

Any ideas? I'd really appreciate quick clues as I'm short of time for this project.

Thanks! Marcepan

CODE AFTER EDITION:

public int partition(Comparable[] a, int left, int right) {
 // Partition a[left…right] such that

 // a[left…p-1] are all less than or equal to a[p]

 // and a[p+1…right] are all greater than or equal to

 // a[p]. Return p.

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

 return j;

}

Instead of a < b, you write a.compareTo(b) < 0.

Other comparison operators are written similarly, so

a[i] <= pivot

becomes

a[i].compareTo(pivot) <= 0

You need to use the compareTo() method on comparable instead:

So a<b becomes a.compareTo(b)<0. The compareTo method would return <0 if a is less than b, 0 if they're the same and >0 if a is more than b.

This is required because Java doesn't support operator overloading, so operators such as less than, greater than etc. can only be used on primitive types (with some exceptions such as with strings), not any library classes or interfaces.

As a side point, if you're using this in practice and not just for academic purposes then using Collections.sort() is almost always going to be faster than your own implementation!

I would use the same code you have written

int comp = a[r].compareTo(pivot);
if (comp < 0) {

They are Comparable objects, so you can't use <= .. you should use the compareTo method.

while i <= j and ( a[i].compareTo(pivot) <= 0 )