Cody Cody - 1 month ago 12
Java Question

Using quickSort to sort an Integer Vector in only one method (without medianof3 or partition methods, like classical implementations)

Not sure what I'm doing wrong here. I'm getting a null pointer exception. I've tried tweaking a few things, and I also have a version that compiles, but seems to sort the first half of the vector, then it assigns null values to half the indexes, therefore I think there is something fundamentally wrong with my code.

As stated in the title, I am attempting to do this in only one method. Middle is simply defined as the median element, (left+right)/2. I am attempting to do the partitioning via a for loop, rather than a separate partition method.

I have referred to: Stackoverflow with Quicksort Java implementation

Mainly the accepted response by raymi (hence the //ei=right, in my code)

I am not sure what I am doing differently...is his code not correct, or is it me?

Here's my code:

public static void quickSort(Vector v, int left, int right) {
//ei = right
//si == left

if(left == right){
return;}
//base case -- no more recursion!!
else{
Comparable pivot = (Comparable) v.elementAt((left+right)/2);
int i;
i = left + 1;

//partition the array
for(int j = left +1; j<= right; j++){
if(pivot.compareTo(v.elementAt(j)) > 0){
swap(v, left, j);
i++;
}//end if
}//close for loop
//place pivot in the right position
//may be incorrect(?)
v.replace(left, v.elementAt(i-1));
v.replace(i-1, v.elementAt((Integer) pivot));

//recursive call on both sides -- may be wrong(?)
quickSort(v, left, i-2);
quickSort(v, i, right);
}
}//end quicksort


and my swap replace code, which works fine in other methods:

public void replace(int indexGiven, Object element){
if(indexGiven<0 || indexGiven>= size)
return false;

data[indexGiven] = element;
return true;
}


When I run the code, I get a null pointer exception. I've played around with swapping "> to <" and things like that, but at best I have gotten the code to compile and assign null values to half the vector. I think there's some obvious wrong with my code, but I just can't see it.

Answer

The final code example is similar to Hoare partition scheme. It should start off

    for(i = low-1, j = high+1 ; ;)

since the first while preincrements i and the second while predecrements j. The pivot value can be from any value in the array (such as pivot = a[(low + high)/2]), but the actual pivot index used will be based on j, the recursive calls will be

    quicksort(a, low, j);
    quicksort(a, j+1, high);

Side note - you could use a median of 3 to sort a[low], a[(low + high)/2], a[high] (3 if / swap statements), then use pivot = a[(low + high)/2].