p.minguzzi
10-13-2005, 06:04 AM
I found a problem with the Shell subroutine of Chapter 8.1
(Fortran 77): in the rare case when the dimension N of the array A is exactly (3^k-1)/2 the algorithm accesses the location A(N+1), which in principle is undefined and can contain any value. If it happens that this alien value is smaller than all the elements of the array it will be inserted at the first place in the sorted array.
These statements can be checked by the following simple example. Let us assume that we have a 5 element set A={1,5,2,7,0} and we want to sort the subset {1,5,2,7} of the first 4 elements of A, then a call Shell(4,A) will produce this output: {0,2,5,7}.
For just this case a correct answer is otherwise obtained if in the first IF statement .LE. is changed to .LT. ; however it is not clear to me whether this is the correct fix for every situation.
P. Minguzzi
(Fortran 77): in the rare case when the dimension N of the array A is exactly (3^k-1)/2 the algorithm accesses the location A(N+1), which in principle is undefined and can contain any value. If it happens that this alien value is smaller than all the elements of the array it will be inserted at the first place in the sorted array.
These statements can be checked by the following simple example. Let us assume that we have a 5 element set A={1,5,2,7,0} and we want to sort the subset {1,5,2,7} of the first 4 elements of A, then a call Shell(4,A) will produce this output: {0,2,5,7}.
For just this case a correct answer is otherwise obtained if in the first IF statement .LE. is changed to .LT. ; however it is not clear to me whether this is the correct fix for every situation.
P. Minguzzi