My quicksorting algorithm seems like it should all be in order and work just fine, but I'm getting a NPE when I try to sort a list of random ints. What exactly am I doing wrong??
public ArrayList<Integer> quickSort(ArrayList<Integer> list, int l, int r){
ArrayList<Integer> sortedList = new ArrayList<Integer>();
while(l<r){
int partVal = partition(list, l, r, 0);
sortedList = quickSort(list, l, partVal-1);
sortedList = quickSort(list, partVal+1, r);
}
return sortedList;
}
public int partition(ArrayList<Integer> list, int l, int r, int pivot){
int pivotVal = list.get(pivot);
swapElements(list, pivot, r);
int counter = l;
for(int i = l; i < r; i++){
int pos = list.get(i);
if(pos <= pivotVal){
swapElements(list, i, counter);
counter++;
}
}
swapElements(list, r, counter);
return counter;
}
public void swapElements(ArrayList<Integer> list, int a, int b){
int temp = list.get(a);
开发者_如何转开发 list.replace(a, list.get(b));
list.replace(b, temp);
}
Let's start with this:
while (l < r) {
int partVal = partition(list, l, r, 0);
sortedList = quickSort(list, l, partVal-1);
sortedList = quickSort(list, partVal+1, r);
}
How are you expecting the loop to ever terminate? The values of l
and r
don't change, so the condition isn't going to become false.
It's not clear why you're looping at all... the point is that the recursive call does the work. I suspect you want an if
here instead. You've said in a comment that you then end up with a NullPointerException
, which you should give details of. Step through your code carefully, working out what you expect it to do and what it's actually doing.
you are sorting the array inplace no need to return a new list
public ArrayList<Integer> quickSort(ArrayList<Integer> list, int l, int r){
if(r<l)return list;
int partVal = partition(list, l, r, l);
quickSort(list, l, partVal-1);
quickSort(list, partVal+1, r);
return list;
}
精彩评论