Sorting algorithms/Insertion sort: Difference between revisions
Sorting algorithms/Insertion sort (view source)
Revision as of 03:50, 28 December 2017
, 6 years ago→{{header|Fortran}}: Acknowledge the vagueness of the modern specification.
(Added Algol W) |
(→{{header|Fortran}}: Acknowledge the vagueness of the modern specification.) |
||
Line 1,194:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<lang fortran>PURE SUBROUTINE Insertion_Sort(a)
Line 1,204 ⟶ 1,203:
j = i - 1
temp = a(i)
DO WHILE (j>=1 .AND. a(j)>temp) !May fail if both sides are evaluated.
a(j+1) = a(j)
j = j - 1
Line 1,214 ⟶ 1,213:
<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
END DO
a(j+1:i) = cshift(a(j+1:i),-1)
END DO</lang>
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.]]
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.
Otherwise, the nice "structured" WHILE-loop would have to be re-written, perhaps as follows:
=== Alternate Fortran 77 version ===
<lang fortran> SUBROUTINE SORT(N,A)
IMPLICIT NONE
INTEGER N,I,J
DOUBLE PRECISION A(N),X
DO 30 I = 2,N
X = A(I)
J = I
10 J = J - 1
Can't IF
IF (A(J).LE.X) GO TO
GO TO 10
20 A(J + 1) = X
30 CONTINUE
END</lang>
| |||