Sorting algorithms/Insertion sort: Difference between revisions
Sorting algorithms/Insertion sort (view source)
Revision as of 01:39, 30 December 2017
, 6 years ago→{{header|Fortran}}: In response to eoraptor
(→{{header|Fortran}}: acknowledging it does not make it correct: it is not) |
(→{{header|Fortran}}: In response to eoraptor) |
||
Line 1,199:
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
INTEGER :: i, j
DO i = 2, SIZE(a)
j = i - 1
Line 1,224 ⟶ 1,223:
If array bound checking is not active, then there will be no difficulties as the invalid array location is only read from, though some systems (such as the B6700 with unrelenting hardware-based bound checking) might still detect an out-of-bounds condition and end the run. A given compiler might, for this case, produce a short-circuit escape, but this is unlikely to be clearly documented in the manual, even if the manual is read by the programmer.
A test run with array-bound checking active raised no difficulties with the code produced by the Compaq Visual Fortran 6.6 F90/95 compiler, and the sort worked, and J = 0 did happen (test data 3,1,4,1,5,9) - inspection of the code showed that j >= 1 was tested first, and, if the result were ''false'', the rest of the .OR. was ignored.
Otherwise, the nice "structured" WHILE-loop would have to be re-written, perhaps as follows:▼
▲Otherwise, the nice "structured" WHILE-loop would have to be re-written, perhaps as follows: <lang Fortran>PURE SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
INTEGER :: i, j
DO i = 2, SIZE(a)
j = i - 1
temp = a(i)
! DO WHILE (j>=1 .AND. a(j)>temp) !May fail if both sides are evaluated.
666 if (a(j) > temp) then
a(j+1) = a(j)
j = j - 1
if (j > 0) go to 666
end if
! END DO
a(j+1) = temp
END DO
</lang>
The commented-out DO WHILE ... END DO could be removed for clarity, though if absent, someone might revise the code to gain "structure" and re-introduce the problem. Note that the revised code is ''not'' the equivalent of the DO WHILE ... END DO code, because of the absence of the test on j the first time around. This is unnecessary, because j is initialised to i - 1 and the minimum value of i is 2, therefore it is a waste of effort to test for this. Difficulties with the starting arrangements for DO WHILE loops are frequent. As well, the test on j at the end allows the test to be j > 0, rather than the j >= 1 at the start and a comparison against zero, a special value, should be possible without a subtraction. So, one spurious test is avoided, and the other tests should be faster: compensation for the appearance of a label and ... a GO TO?
=== Alternate Fortran 77 version ===
This also could have a problem with the compound test always being fully evaluated, so... <lang fortran> SUBROUTINE SORT(N,A)
IMPLICIT NONE
INTEGER N,I,J
Line 1,235 ⟶ 1,253:
J = I
10 J = J - 1
Can't IF (J.EQ.0 .OR. A(J).LE.X) GO TO 20 in case both sides are ALWAYS evaluated.
IF (J.EQ.0) GO TO 20
IF (A(J).LE.X) GO TO 20
| |||