# Counting # of comparisons in a quick sort and printing them

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!!
Jo

``````//Quick sort algorithm.
//Postcondition: list objects are in ascending order.
public void quickSort(T[] list, int length)
{
recQuickSort(list, 0, length - 1);
}//end quickSort

//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
//               returned.
private int partition(T[] list, int first, int last)
{
T pivot;

int smallIndex;
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)
{
smallIndex++;
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);

return smallIndex;

}
//end partition

//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);

}

}//end recQuickSort
``````
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Make 'counter' an instance variable and do
``````    //Quick sort algorithm.
//Postcondition: list objects are in ascending order.
public void quickSort(T[] list, int length) {
recQuickSort(list, 0, length - 1);
System.out.printf("The total number of comparisons in the quickSort was %d\n", counter);
} //end quickSort
``````
0
Author Commented:
Thanks!
It looks like it would work, but when I paste it in and run the programs, it says it can't find counter (which it can't because counter get initialized later).
Have I just messed up copying your code into my program? I'll attach the folder with the SearchSortAlgorithms, SearchSortADT and my test file
ExamInsertionQuickSort4-files--2.zip
0
Commented:
>>it says it can't find counter (which it can't because counter get initialized later).

It must be an instance variable of the class containing the sorting methods
0
Java DeveloperCommented:

//Quick sort algorithm.

// make counter a member variable

private int counter = 0;         //initialize counter

//Postcondition: list objects are in ascending order.
public void quickSort(T[] list, int length)
{
recQuickSort(list, 0, length - 1);
// print out counter once all done
System.out.print(counter);   // print out number of comparisons
System.out.print("The total number of comparisons in the quickSort was  ");

}//end quickSort

//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
//               returned.
private int partition(T[] list, int first, int last)
{
T pivot;

int smallIndex;
swap(list, first, (first + last) / 2);

pivot = list[first];
smallIndex = first;

for (int index = first + 1; index <= last; index++)
{
Comparable compElem = (Comparable) list[index];
counter=counter+1;        //increment counter

if (compElem.compareTo(pivot) < 0)
{
smallIndex++;
swap(list, smallIndex, index);

}

}

swap(list, first, smallIndex);

return smallIndex;

}
//end partition

//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);

}

}//end recQuickSort
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
Thank you!  Great solution! It works perfectly and I have learned something new.

Many, many thanks!!!
Jo
0
Author Commented:
Great solution that worked perfectly and taught me a new bit about Java as well.
0
Author Commented:
Hi,
I'm new at this.
I meant to assign 400 point to object for an outstanding solution and 100 point to CEHJ for making a great suggestion based onmy llimited input.

If I didn't get them assigned like that,would you let me know or fix it?

I REALLY appreciate the help!
0
Commented:
>>I meant to assign 400 point to object for an outstanding solution and 100 point to CEHJ

I find that odd. The only difference between what i posted and objects posted is that he's repeated more of your code, and showed the instance variable, which i didn't think necessary.

>>If I didn't get them assigned like that,would you let me know or fix it?

I'll get the question reopened
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.