Make this QuickSort Java Program better [closed]
Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 11 years ago.
Improve this questionI have this QuickSort program, I am thinking maybe it's not the best solution, I want ideas on Optimizations I could do. I plan on running it on about 20Million integer numbers.
public static ArrayList<Comparable> quickSort(ArrayList<Comparable> arrayToSort) {
if(arrayToSort.size() <= 0) {
return arrayToSort;
}
Comparable pivot = arrayToSort.get(0);
arrayToSort.remove(pivot);
return quickSort(arrayToSort, pivot);
}
private static ArrayList<Comparable> quickSort(ArrayList<Comparable> arrayToSort, Comparable pivot) {
ArrayList<Comparable> smaller = new ArrayList<Comparable>();
ArrayList<Comparable> bigger = new ArrayList<Comparable>();
for(Comparable i: arrayToSort) {
if(i.compareTo(pivot) > 0) {
bigger.add(i);
} else {
smaller.add(i);
}
}
ArrayList<Comparable> retVal = new ArrayList<Comparable>();
retVal.addAll(quickSort(smaller));
retVal.add(pivot);
retVal.addAll(quickSort(bigger));
return retVal;
}
Thanks
- Use introsort instead quicksort.
- Use median-of-three or randomized pivot selection.
- Parallelize using Fork/Join.
精彩评论