|
=={{header|Fortran}}==
{{incorrect|Fortran|The .AND. operator is not "short-circuit", hence the test "a(j)>temp" may crash the program}}
{{works with|Fortran|90 and later}}
<lang fortran>PURE SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
INTEGER :: i, j
DO WHILE (j>=1 .AND. a(j)>temp) !May fail if both sides are evaluated.
END DO
a(j+1) = temp
END DO
END SUBROUTINE Insertion_Sort</lang>
In ISO Fortran 90 and above the intrinsic function CSHIFT can be used to shift the elements in the array but in practice is slower than the above example
<lang fortran>DO i = 2, SIZE(a) ▼ j = i - 1
DO WHILE (j>=1 .AND. a(j) > a(i)) !If j = 0, and both sides are evaluated, accessing a(0) may be blocked.
j = j - 1
a(j+1:i) = cshift(a(j+1:i),-1)
END DO</lang>
▲<lang fortran> DOsubroutine i = 2sort(n, SIZE(a)
However, he compound WHILE condition can't be relied upon, because a given compiler might generate code that always evaluates ''both'' sides of an OR expression, even when the result is already determined by the first part. Some compilers always generate "short-circuit" code, or do so in certain situations but not others, or on specification of a compiler option, or may even swap the order of evaluation of the two sides. [[Talk:Short-circuit_evaluation#Compiler_optimisations.3F|The issue is vexing.]]
implicit none
INTEGER integer :: n, i, j ▼
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.
real :: a(n), x
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 machine 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: <lang Fortran>PURE SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
if (a(j > 0) go<= tox) 666exit▼
DO i = 2, SIZE a(j + 1) = a(j)
j = ij - 1
temp = a(i) end do
! DO WHILE (j>=1 .AND. a(j)>temp) !May fail if both sides are evaluated.
666 if (a(j) > temp) then
end subroutine</lang>
a(j+1) = a(j)
j = j - 1
! 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 ===
|