I am trying to sort an ArrayList of integers in numerical order using a quicksort algorithm. The below code is what I have been able to come up with and it is getting close to sorting the list but unfortunately, it does not completely sort my ArrayList as it should. It will come pretty close but it is almost as if it just needs to run the while loop a few more times to completely sort the list. I have been trying for quite a long time now to figure out why my code won't work properly so any help would be appreciated.
Right now these are the results I am getting:
Pre-sort: [9, 2, 10, 3, 6, 7, 4, 8, 5, 1]
Post-sort: [1, 2, 5, 3, 4, 6, 7, 8, 9, 10]
/**
*
* This method performs a quicksort on the generic ArrayList given as input. You
* must implement three different strategies for determining the pivot, and your
* implementation should be able to easily switch among these strategies.
* (Consider using a few private helper methods for your different
* pivot-selection strategies.) You will perform timing experiments to determine
* which strategy works best. Your implementation may switch to insertion sort
* on some small threshold, if you wish.
*
* @param <T>
*/
static <T extends Comparable<? super T>> void quickSort(ArrayList<T> quickList, int begin, int end) {
if (begin < end) {
int partitionIndex = partition(quickList, begin, end);
quickSort(quickList, begin, partitionIndex - 1);
quickSort(quickList, partitionIndex 1, end);
}
}
private static <T extends Comparable<? super T>> int partition(ArrayList<T> quickList, int begin, int end) {
int init = begin;
int length = end;
int pivot = quicksort.getRandom(quickList);
while (true) {
while ((int) quickList.get(length) > (int) pivot && length > begin) {
length--;
}
while ((int) quickList.get(init) < (int) pivot && init < end) {
init ;
}
if (init < length) {
T temp;
temp = quickList.get(init);
quickList.set(init, quickList.get(length));
quickList.set(length, temp);
length--;
init ;
} else {
return length;
}
}
}
public interface quicksort {
/**
* This method will grab the median of the entire ArrayList
*
* @return median
*/
static <T> int getMedian(ArrayList<T> passedArrayList) {
double lower = 0;
double upper = 0;
if (passedArrayList.size() % 2 == 1)
System.out.println(passedArrayList.get((passedArrayList.size() 1) / 2 - 1));
else {
// Will make sure that our passed array is able to be divided
lower = (double) (passedArrayList.size() / 2 - 1);
upper = (double) (passedArrayList.size() / 2);
}
return (int) Math.round((lower upper) / 2.0);
}
/**
* This method will randomly grab a index out of the provided ArrayList
*
* @param <T>
* @return median
*/
static <T> int getRandom(ArrayList<T> passedArrayList) {
int arrayListSize = passedArrayList.size();
Random rand = new Random(); // instance of random class
int upperbound = arrayListSize;
int randomIndex = rand.nextInt(upperbound);
return randomIndex;
}
/**
* This method will grab three random indexes and then determine the median
* based off of those
*
* @return median
*/
static <T> int getThreeRandomThenMedian(ArrayList<T> passedArrayList) {
int[] intArray;
intArray = new int[3];
// sets are array with 3 random numbers from our passedArrayList
intArray[0] = getRandom(passedArrayList);
intArray[1] = getRandom(passedArrayList);
intArray[2] = getRandom(passedArrayList);
// finds the median of our 3 random numbers
Arrays.sort(intArray);
double median;
if (intArray.length % 2 == 0)
median = ((double) intArray[intArray.length / 2] (double) intArray[intArray.length / 2 - 1]) / 2;
else
median = (double) intArray[intArray.length / 2];
// converts our median from a double to a int so we can grab the median from our
// array
int returnMedian = (int) Math.round(median);
return returnMedian;
}
}
CodePudding user response：
// 3-way quicksort
public final class QuickSort {
public static <T extends Comparable<? super T>> void quickSort(List<T> items) {
Collections.shuffle(items); // sorted array is the worst case
quickSort(items, 0, items.size() - 1);
}
private static <T extends Comparable<? super T>> void quickSort(List<T> items, int lo, int hi) {
if (lo < hi) {
Pair pair = partition(items, lo, hi);
quickSort(items, lo, pair.lt - 1);
quickSort(items, pair.gt 1, hi);
}
}
private static <T extends Comparable<? super T>> Pair partition(List<T> items, int lo, int hi) {
int lt = lo;
int i = lo 1;
int gt = hi;
T item = items.get(lo);
while (i <= gt) {
int cmp = items.get(i).compareTo(item);
if (cmp < 0)
swap(items, lt , i );
else if (cmp > 0)
swap(items, i, gt--);
else
i ;
}
return new Pair(lt, gt);
}
private static <T> void swap(List<T> items, int i, int j) {
T tmp = items.get(i);
items.set(i, items.get(j));
items.set(j, tmp);
}
private static final class Pair {
private int lt;
private int gt;
public Pair(int lt, int gt) {
this.lt = lt;
this.gt = gt;
}
}
private QuickSort() {
}
}
Demo
List<Integer> items = Arrays.asList(9, 2, 10, 3, 6, 7, 4, 8, 5, 1);
System.out.println(items); // [9, 2, 10, 3, 6, 7, 4, 8, 5, 1
QuickSort.quickSort(items);
System.out.println(items); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. - 2.3 Quicksort is your friend!