 Selection Sort
This function sorts an array using the algorithm known as selection sort. The array is composed of elements of type int, holding a single integer. Because C has no way to determine the number of elements in an array, this is passed as a second argument to the function.
Selection sort uses two nested loops. The first time through the outer loop, the inner loop finds the element in the array that has the lowest number. It then swaps that element with the element in the first position in the array, so that the first element now has the lowest number in it. The outer loop then iterates again, finding the next lowest number in the array and swapping that into the second position, and so on.
Source Code
1. void sort (
2. int a[],
3. int n) {
4.
5. int current, j, lowestindex, temp;
6.
7. for (current = 0; current < n-1; current++) {
8.
9. //
10. // each time through this loop, scan the array
11. // from current+1 to the end. If we find
12. // something lower than what is at current, then
13. // swap it with current index. So each time
14. // through this loop, a[current] will be
15. // properly sorted.
16. //
17. // 1) first find the index of the lowest value
18. //
19. // If lowestindex remains unchanged, a[current]
20. // is already sorted.
21. //
22.
23. lowestindex = current;
24.
25. for (j = current+1; j < n; j++) {
26. if (a[j] < a[current]) {
27. lowestindex = j;
28. }
29. }
30.
31. //
32. // 2) now swap a[current] and a[lowestindex],
33. // as long as a difference was found.
34. //
35.
36. if (lowestindex != current) {
37. temp = a[current];
38. a[current] = a[lowestindex];
39. a[lowestindex] = temp;
40. }
41. }
42. }
Suggestions
The code has six variables (the locals current, j, lowestindex, and temp, plus the two parameters a and n). Classify the variables according to how they change. Are they invariant throughout the entire function? Are they invariant through one instantiation of the outer loop? Are they invariant through one instantiation of the inner loop? Is their use localized to one (or more) subsections of the code? This code has three main comments (two of which are next to each other). Verify that the comments match what the code attempts to do. The code on lines 36-40 has several variables that appear in quick succession on the left and right sides of assignments. This is a good place to check to ensure that the logic is correct. What are the empty, trivial, and already solved inputs to this function?
Hints
Walk through the code with the following parameters to the function:
The elements are already sorted:
a[0] == 2
a[1] == 5
a[2] == 8
a[3] == 20 n is equal to 4. Two values are equal:
a[0] == 4
a[1] == 2
a[2] == 3
a[3] == 4 n is equal to 4. An array of numbers are all different and partly out of order:
a[0] == 3
a[1] == 1
a[2] == 2
a[3] == 4
n is equal to 4.
Explanation of the Bug
In the inner loop, the comparison on line 26
if (a[j] < a[current]) is incorrect. The algorithm is designed so that at the end of each iteration of the outer loop, starting at line 36, it will swap a[current] with the lowest-valued array element that appears after current in the array. But as it is written now, it will swap it with the last element in the array that is less than a[current].
For example, look at hint #3, where the array is equal to:
[3, 1, 2, 4 ]
During the first iteration of the outer loop, when current is 0, the end result should be to swap the 3 in the first position with the 1 in the second position, because 1 is the smallest element in the array. Consider what actually happens in the inner loop (lines 25-29), the way the code is now written. current is 0 and j loops from 1 to 3. When j is 1, the code on line 26 compares a[0] to a[1], and correctly determines that lowestindex should be set to 1 at line 27. However, when j is 2 and the code on line 26 compares a[0] to a[2], line 27 then (incorrectly) updates lowestindex to 2. When j is 3, lowestindex remains unchanged, so lowestindex is still 2 when the code reaches the swap routine at line 36. The swap code exchanges the 3 and the 2 in the array, which is incorrect.
To fix this, change the test on line 26 to the following:
if (a[j] < a[lowestindex])
This ensures that lowestindex is updated only if a new value is found that is lower than the current lowest value. This bug could either be B.variable or A.logic; it depends whether the programmer used the wrong variable by accident or on purpose.
|
