For part of a homework, my program has to output the number of comparisons of data elements made by a quick sort and an insertion sort. I got the insertion sort to work. Not so the quick sort.
I have added a counter to the quickSort method provided, but it is in a loop and just keeps printing forever. I have tried putting the counter elsewhere and get an "unreachable" error.
Would you please look at my code and tell me where I have messed up?
I can provide the program where I call the quickSort function if that helps.
Many, many thanks for helping me get this straight!!
//Quick sort algorithm.
//Postcondition: list objects are in ascending order.
public void quickSort(T list, int length)
recQuickSort(list, 0, length - 1);
//Method to partition the list between first and last.
//The pivot is choosen as the middle element of the list.
//This method is used by the recQuickSort method.
//Postcondition: After rearranging the elements,
// according to the pivot, list elements
// between first and pivot location - 1,
// are smaller the the pivot and list
// elements between pivot location + 1 and
// last are greater than or equal to pivot.
// The position of the pivot is also
private int partition(T list, int first, int last)
int counter = 0; //initialize counter
swap(list, first, (first + last) / 2);
pivot = list[first];
smallIndex = first;
for (int index = first + 1; index <= last; index++)
Comparable<T> compElem = (Comparable<T>) list[index];
counter=counter+1; //increment counter
if (compElem.compareTo(pivot) < 0)
swap(list, smallIndex, index);
System.out.print(counter); // print out number of comparisons
System.out.print("The total number of comparisons in the quickSort was ");
swap(list, first, smallIndex);
//Method to sort the elements of list between first
//and last using quick sort algorithm,
//Postcondition: list elements between first and last
// are in ascending order.
private void recQuickSort(T list, int first, int last)
if (first < last)
int pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation - 1);
recQuickSort(list, pivotLocation + 1, last);