CS1103 Programming Assignment Unit 4 - Debugging

Posted on | In | Views
CS1103 Programming Assignment Unit 4.

Questions

Use the debugger to find all bugs in the file BuggySearchAndSort.java and write a report.

1. The program with bugs

BuggySearchAndSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import java.util.Arrays;

/**
 * This class looks like it's meant to provide a few public static methods
 * for searching and sorting arrays.  It also has a main method that tests
 * the searching and sorting methods.
 * 
 * TODO: The search and sort methods in this class contain bugs that can
 * cause incorrect output or infinite loops.  Use the Eclipse debugger to 
 * find the bugs and fix them
 */
public class BuggySearchAndSort {
	
	public static void main(String[] args) {
		
		int[] A = new int[10];  // Create an array and fill it with small random ints.
		for (int i = 0; i < 10; i++)
			A[i] = 1 + (int)(10 * Math.random());
		
		int[] B = A.clone();   // Make copies of the array.
		int[] C = A.clone();
		int[] D = A.clone();
		
		System.out.print("The array is:");
		printArray(A);
		
		if (contains(A,5))
			System.out.println("This array DOES contain 5.");
		else
			System.out.println("This array DOES NOT contain 5.");
		
		Arrays.sort(A);  // Sort using Java's built-in sort method!
		System.out.print("Sorted by Arrays.sort():  ");
		printArray(A);   // (Prints a correctly sorted array.)

		bubbleSort(B);
		System.out.print("Sorted by Bubble Sort:    ");
		printArray(B);

		selectionSort(C);
		System.out.print("Sorted by Selection Sort: ");
		printArray(C);
		
		insertionSort(D);
		System.out.print("Sorted by Insertion Sort: ");
		printArray(D);

	}
	
	/**
	 * Tests whether an array of ints contains a given value.
	 * @param array a non-null array that is to be searched
	 * @param val the value for which the method will search
	 * @return true if val is one of the items in the array, false if not
	 */
	public static boolean contains(int[] array, int val) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] == val)
				return true;
			else
				return false;
		}
		return false;
	}
	
	/**
	 * Sorts an array into non-decreasing order.  This inefficient sorting
	 * method simply sweeps through the array, exchanging neighboring elements
	 * that are out of order.  The number of times that it does this is equal
	 * to the length of the array.
	 */
	public static void bubbleSort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length-1; i++) {
				if (array[j] > array[j+1]) { // swap elements j and j+1
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}
	
	/**
	 * Sorts an array into non-decreasing order.  This method uses a selection
	 * sort algorithm, in which the largest item is found and placed at the end of 
	 * the list, then the second-largest in the next to last place, and so on.
	 */
	public static void selectionSort(int[] array) {
		for (int top = array.length - 1; top > 0; top--) {
			int positionOfMax = 0;
			for (int i = 1; i <= top; i++) {
				if (array[1] > array[positionOfMax])
					positionOfMax = i;
			}
			int temp = array[top];  // swap top item with biggest item
			array[top] = array[positionOfMax];
			array[positionOfMax] = temp;
		}
	}
	
	/**
	 * Sorts an array into non-decreasing order.  This method uses a standard
	 * insertion sort algorithm, in which each element in turn is moved downwards
	 * past any elements that are greater than it.
	 */
	public static void insertionSort(int[] array) {
		for (int top = 1; top < array.length; top++) {
			int temp = array[top];  // copy item that into temp variable
			int pos = top - 1;
			while (pos > 0 && array[pos] > temp) {
				   // move items that are bigger than temp up one position
				array[pos+1] = array[pos];
				pos--;
			}
			array[pos] = temp;  // place temp into last vacated position
		}
	}
	
	/**
	 * Outputs the ints in an array on one line, separated by spaces,
	 * with a line feed at the end.
	 */
	private static void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(" ");
			System.out.print(array[i]);
		}
		System.out.println();
	}

}

2. Report

2.1 Bug 1

2.1.1 The description of the bug

After running the BuggySearchAndSort.java, the code cannot stop, and the program’s output is as follows: 

1
2
3
4
5
The array is: 3 5 1 10 10 1 2 7 2 10
This array DOES NOT contain 5.
Sorted by Arrays.sort():   1 1 2 2 3 5 7 10 10 10

Process finished with exit code 130

The first bug is that the element that needs to be checked is in the array, but the output shows that it is not. Based on the output above, I located the contains() method that caused the bug. This bug is a semantic error because the output is different from what we expected, and the program does not terminate abnormally.

2.1.2 The method to fix it

The code with bugs:

1
2
3
4
5
6
7
8
9
public static boolean contains(int[] array, int val) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == val)
            return true;
        else
            return false;
    }
    return false;
}

The above code will only judge whether the first number in the array is equal to the number to be queried. If the first number in the array is equal to the number to be queried, the program will return true. If not, it will return false. Therefore, the program does not check for numbers except for the first number in the array.

The code without bugs:

1
2
3
4
5
6
7
public static boolean contains(int[] array, int val) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == val)
            return true;
    }
    return false;
}

The fixed code is shown above. To fix this bug, remove the else clause of the if statement so that the code will check all the numbers in the array until it finds the one to query.

2.1.3 Steps to find the bug

According to the outputs, I navigated to line 29 of the code, added a breakpoint there, and clicked the debug button to debug. When the code is paused at line 29, I click the step into button to enter the contains() method, and then run the code step by step, and find that the code will jump out of the for loop after checking the first number of the array, not after checking all the numbers of the array. Therefore, removing the else branch of the for statement can fix the bug.

2.2 Bug 2

2.2.1 The description of the bug

The second bug is that the code cannot be stopped after running. According to the output, after printing the result of Arrays.sort(), there is no information output, so I suspect that the infinite loop is in the code after printing the result of Arrays.sort(). Therefore, I locate the bubbleSort() method in the main().

2.2.2 The method to fix it

The code with bugs:

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - 1; i++) {
            if (array[j] > array[j + 1]) { // swap elements j and j+1
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

In the above code, there is a nested for loop. Because the variable j in the second for loop has not been updated, it becomes an infinite loop.

The code without bugs:

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - 1; j++) {
            if (array[j] > array[j + 1]) { // swap elements j and j+1
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

To fix this bug, we can replace the variable i with j in the second for loop. Then after the value of j is greater than array.length - 1, the loop will end.

2.2.3 Steps to find the bug

First, according to the output, I located the place where the bubbleSort() method was called in the main() method and added a breakpoint there. Then I clicked the “step into” button to debug step by step and found that the second for loop cannot end, and the value of the updated variable j was not updated. The reason is that the updated variable is i instead of j. Therefore, replacing i++ with j++ can fix this bug.

2.3 Bug 3

2.3.1 The description of the bug

The third bug is that in the selectionSort() method, when using the for loop to traverse the array, array[i] is written as array[1], resulting in the output not being sorted in non-descending order.

2.3.2 The method to fix it

The code with bugs:

1
2
3
4
5
6
7
8
9
10
11
12
public static void selectionSort(int[] array) {
   for (int top = array.length - 1; top > 0; top--) {
      int positionOfMax = 0;
      for (int i = 1; i <= top; i++) {
         if (array[1] > array[positionOfMax])
            positionOfMax = i;
      }
      int temp = array[top];  // swap top item with biggest item
      array[top] = array[positionOfMax];
      array[positionOfMax] = temp;
   }
}

The code without bugs:

1
2
3
4
5
6
7
8
9
10
11
12
public static void selectionSort(int[] array) {
    for (int top = array.length - 1; top > 0; top--) {
        int positionOfMax = 0;
        for (int i = 1; i <= top; i++) {
            if (array[i] > array[positionOfMax])
                positionOfMax = i;
        }
        int temp = array[top];  // swap top item with biggest item
        array[top] = array[positionOfMax];
        array[positionOfMax] = temp;
    }
}

To fix this bug, we just need to replace array[1] in the for loop with array[i]. In this case, the program can traverse the array and find the index corresponding to the maximum value in the array.

2.3.3 Steps to find the bug

After fixing the first two bugs, the output shows that the selectionSort() is incorrect. So I located the selectionSort() method in the main() method and added a breakpoint there. Then I clicked the debug button and the step into button to debug step by step. In the for loop, it turned out that when looking for the index of the maximum value, array[i] is wrongly written as array[1]. Therefore, changing array[1] to array[i] can fix this bug.

2.4 Bug 4

2.4.1 The description of the bug

The fourth bug is that in the condition of the while loop, pos should be greater than or equal to 0, not just greater than 0. Also, when placing temp into last vacated position, the value of temp should be assigned to array[pos +1] instead of array[pos].

2.4.2 The method to fix it

The code with bugs:

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertionSort(int[] array) {
   for (int top = 1; top < array.length; top++) {
      int temp = array[top];  // copy item that into temp variable
      int pos = top - 1;
      while (pos > 0 && array[pos] > temp) {
            // move items that are bigger than temp up one position
         array[pos+1] = array[pos];
         pos--;
      }
      array[pos] = temp;  // place temp into last vacated position
   }
}

The code without bugs:

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertionSort(int[] array) {
    for (int top = 1; top < array.length; top++) {
        int temp = array[top];  // copy item that into temp variable
        int pos = top - 1;
        while (pos >= 0 && array[pos] > temp) {
            // move items that are bigger than temp up one position
            array[pos + 1] = array[pos];
            pos--;
        }
        array[pos + 1] = temp;  // place temp into last vacated position
    }
}

To fix this bug, we need to replace pos > 0 in the for loop with pos >= 0, and use “array[pos] = temp” to replace “array[pos + 1] = temp”. In this case, the insertionSort() can sort an array into non-decreasing order.

2.4.3 Steps to find the bug

After fixing the first third bugs, the output shows that the insertionSort() is incorrect. So I located the insertionSort() method in the main() and added a breakpoint there. Then I clicked the debug button and the step into button to debug step by step. After some debugging, I found that in the condition of the while loop, the pos > 0 is incorrect, and it should be changed to pos >= 0. Besides, when placing temp into last vacated position, the statement array[pos] = temp is incorrect, and it should be changed to array[pos + 1] = temp.

3. The program without bugs

Codes: BuggySearchAndSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.util.Arrays;

/**
 * This class looks like it's meant to provide a few public static methods
 * for searching and sorting arrays.  It also has a main method that tests
 * the searching and sorting methods.
 * <p>
 * TODO: The search and sort methods in this class contain bugs that can
 * cause incorrect output or infinite loops.  Use the Eclipse debugger to
 * find the bugs and fix them
 */
public class BuggySearchAndSort {

    public static void main(String[] args) {

        int[] A = new int[10];  // Create an array and fill it with small random ints.
        for (int i = 0; i < 10; i++)
            A[i] = 1 + (int) (10 * Math.random());

        int[] B = A.clone();   // Make copies of the array.
        int[] C = A.clone();
        int[] D = A.clone();

        System.out.print("The array is:");
        printArray(A);

        if (contains(A, 5))
            System.out.println("This array DOES contain 5.");
        else
            System.out.println("This array DOES NOT contain 5.");

        Arrays.sort(A);  // Sort using Java's built-in sort method!
        System.out.print("Sorted by Arrays.sort():  ");
        printArray(A);   // (Prints a correctly sorted array.)

        bubbleSort(B);
        System.out.print("Sorted by Bubble Sort:    ");
        printArray(B);

        selectionSort(C);
        System.out.print("Sorted by Selection Sort: ");
        printArray(C);

        insertionSort(D);
        System.out.print("Sorted by Insertion Sort: ");
        printArray(D);

    }

    /**
     * Tests whether an array of ints contains a given value.
     *
     * @param array a non-null array that is to be searched
     * @param val   the value for which the method will search
     * @return true if val is one of the items in the array, false if not
     */
    public static boolean contains(int[] array, int val) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == val)
                return true;
//            else
//                return false;
        }
        return false;
    }

    /**
     * Sorts an array into non-decreasing order.  This inefficient sorting
     * method simply sweeps through the array, exchanging neighboring elements
     * that are out of order.  The number of times that it does this is equal
     * to the length of the array.
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) { // swap elements j and j+1
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /**
     * Sorts an array into non-decreasing order.  This method uses a selection
     * sort algorithm, in which the largest item is found and placed at the end of
     * the list, then the second-largest in the next to last place, and so on.
     */
    public static void selectionSort(int[] array) {
        for (int top = array.length - 1; top > 0; top--) {
            int positionOfMax = 0;
            for (int i = 1; i <= top; i++) {
                if (array[i] > array[positionOfMax])
                    positionOfMax = i;
            }
            int temp = array[top];  // swap top item with biggest item
            array[top] = array[positionOfMax];
            array[positionOfMax] = temp;
        }
    }

    /**
     * Sorts an array into non-decreasing order.  This method uses a standard
     * insertion sort algorithm, in which each element in turn is moved downwards
     * past any elements that are greater than it.
     */
    public static void insertionSort(int[] array) {
        for (int top = 1; top < array.length; top++) {
            int temp = array[top];  // copy item that into temp variable
            int pos = top - 1;
            while (pos >= 0 && array[pos] > temp) {
                // move items that are bigger than temp up one position
                array[pos + 1] = array[pos];
                pos--;
            }
            array[pos + 1] = temp;  // place temp into last vacated position
        }
    }

    /**
     * Outputs the ints in an array on one line, separated by spaces,
     * with a line feed at the end.
     */
    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(" ");
            System.out.print(array[i]);
        }
        System.out.println();
    }

}

Outputs:

1
2
3
4
5
6
7
8
The array is: 1 3 3 1 5 6 8 10 4 5
This array DOES contain 5.
Sorted by Arrays.sort():   1 1 3 3 4 5 5 6 8 10
Sorted by Bubble Sort:     1 1 3 3 4 5 5 6 8 10
Sorted by Selection Sort:  1 1 3 3 4 5 5 6 8 10
Sorted by Insertion Sort:  1 1 3 3 4 5 5 6 8 10

Process finished with exit code 0

​

This is the ending, thanks for reading.