with this code, I have to count the number of element comparisons that are made. with that being said, I am not sure that the compare are done within the for loop of the sort() method, or within the less() method. thank you so much for your help.
public class Shell {
private static int compares;
// This class should not be instantiated.
private Shell() { }
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int n = a.length;
// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) {
// h-sort the array
for (int i = h; i < n; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHsorted(a, h);
h /= 3;
}
assert isSorted(a);
}
/*************************************************************************** * Helper sorting functions. ***************************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/*************************************************************************** * Check if array is sorted - useful for debugging. **************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
// is the array h-sorted?
private static boolean isHsorted(Comparable[] a, int h) {
for (int i = h; i < a.length; i++)
if (less(a[i], a[i-h])){
return false;
}
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; Shellsorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Shell.sort(a);
show(a);
}
}
Given that your code looks like the classic student's exercise, probably you're asked to count only the number of element comparisons that are made by less function when is called inside the sort function. If I'm wrong please update your question adding a more complete description of your target.
As you can see, a comparison is made each time less function is called. But in your piece of code less is even the method used commonly to compare two objects. So you should count only when the less function is called directly within the sort method. The other cases isSorted and isHsorted are there only because the assertions.
Just to be clear, assertion are a statements in the Java programming language that enables you to test assumptions about your program.
Remember, this is your exercise, so you shouldn't go looking around for an easy answer and I wouldn't write any detailed code solution.
But I can give you another suggestion, you could try to create a new method lessWithCounter to be called in behalf of less into the sort method.