Hello Stack Overflowers,
I'm stumped on a homework issue where we were tasked to create an "inefficient" quick sort algorithm that was easy to explain and understand using a pivot system and using a median of three technique and then using insertion sort as a cleanup sort. I will attach "SOME" code snippets as to not give away a solution to others attempting this homework, aswell as the output [edit: apparently I am not allowed to post images yet ugh..]. The only problem I am having is that in the final sorting results, the last index is the only unsorted value. the rest seems to work fine. This happens whether I go behind the threshold and just use insertion sort only, or the full quicksort. Any ideas? I've been working on this for a few days and I am probably just suffering from a lack of sleep. A point in the right direction would be wonderful!
int partition(int* list, int start, int stop) {
int index = 0;
int leftPtr = start;
int rightPtr = stop - 1;
while (!(leftPtr >= rightPtr)) {
if (list[leftPtr] <= list[rightPtr]) {
rightPtr--;
}
else {
swap(list, rightPtr, leftPtr);
}
if (list[rightPtr] >= list[leftPtr]) {
leftPtr++;
}
else {
swap(list, leftPtr, rightPtr);
}
}
index = leftPtr;
return index;
}
void quickSort(int* theArray, int startIndex, int stopIndex) {
if (stopIndex - startIndex <= SMALL_LIST_SIZE) {
insertionSort(theArray, startIndex, stopIndex);
}
else {
setMedianOfThree(theArray, startIndex, stopIndex);
int partitionElement = partition(theArray, startIndex, stopIndex);
quickSort(theArray, startIndex, partitionElement - 1);
quickSort(theArray, partitionElement + 1, stopIndex);
}
}
void insertionSort(int* list, int start, int stop) {
if (stop <= 1) {
return;
}
insertionSort(list, stop - 1);
int last = list[stop - 1];
int j = stop - 2;
while (j >= 0 && list[j] > last)
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = last;
}
