I am having trouble adding the ability to order an integer array in both ascending and descending order. I have implemented the functions myself and am having trouble figuring out how to order them in reverse order.
I am passing in a boolean variable to test which direction the array should be ordered, and using a helper method which replaces the operator in the for loop.
Both algorithms work fine for ascending order, but neither work for descending order. I am having trouble finding the comparison that I am not making to make the list descending.
public void mergeSort(int[] array, int lowindex, int highindex,
boolean reversed) {
int[] temp = new int[array.length];
mergeSort(array, temp, lowindex, highindex, reversed);
}
private static void mergeSort(int[] array, int[] temp, int low, int high,
boolean reversed) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(array, temp, low, mid, reversed);
mergeSort(array, temp, mid + 1, high, reversed);
merge(array, temp, low, mid, high, reversed);
}
}
private static void merge(int[] array, int[] temp, int low, int mid,
int high, boolean reversed) {
int insertindex = low;
int lowindex = low;
int highindex = mid + 1;
while (compareInclusive(insertindex, high, reversed)) {
if (compare(mid, lowindex, reversed)) {
temp[insertindex++] = array[highindex++];
} else if (compare(high, highindex, reversed)) {
temp[insertindex++] = array[lowindex++];
} else if (compare(array[lowindex], array[highindex], reversed)) {
temp[insertindex++] = array[lowindex++];
} else {
temp[insertindex++] = array[highindex++];
}
}
for (insertindex = low; insertindex <= high; insertindex++) {
array[insertindex] = temp[insertindex];
}
}
public void quickSort(int[] array, int lowindex, int highindex,
boolean reversed) {
int pivot;
if (compare(lowindex, highindex, reversed)) {
pivot = partition(array, lowindex, highindex, reversed);
quickSort(array, lowindex, pivot - 1, reversed);
quickSort(array, pivot + 1, highindex, reversed);
}
}
static int partition(int[] array, int low, int high, boolean reversed) {
int pivot;
int tmp;
int max = high;
int mid = (low + high) / 2;
tmp = array[mid];
array[mid] = array[high];
array[high] = tmp;
pivot = array[high];
low--;
do {
while (array[++low] < pivot)
;
while ((low < high) && (array[--high] > pivot))
;
tmp = array[low];
array[low] = array[high];
array[high] = tmp;
} while (low < high);
tmp = array[low];
array[low] = array[max];
array[max] = tmp;
return low;
}
public static boolean compare(int smaller, int larger, boolean reversed) {
if (reversed) {
if (smaller > larger) {
return true;
}
} else {
if (smaller < larger) {
return true;
}
}
return false;
}
public static boolean compareInclusive(int smaller, int larger,
boolean reversed) {
if (reversed) {
if (smaller >= larger) {
return true;
}
} else {
if (smaller <= larger) {
return true;
}
}
return false;
}