im trying to count the number of comparisons in a shellsort method, but im strug
ID: 3791368 • Letter: I
Question
im trying to count the number of comparisons in a shellsort method, but im struggling to create a counter and get the counter to print. here is the code i am working with.
public class Shell {
// 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);
System.out.println(compares);
}
/***************************************************************************
* 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 = new String[10];
Shell.sort(a);
show(a);
}
}
Explanation / Answer
Hi, I have added a Counter to count the number of comparison.
Please let me know in case of any issue.
public class Shell {
// a private inner static class to keep number of comparison
private static class Counter{
static int data = 0;
}
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);
System.out.println(Counter.data);
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
Counter.data++; // increasing comparison counter
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++){
// increasing comparison counter
Counter.data++;
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++){
Counter.data++; // increasing comparison counter
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 = new String[10];
Shell.sort(a);
show(a);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.