Sorting algorithms/Heapsort: Difference between revisions

=={{header|BCPL}}==

<lang BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.

GET "libhdr.h"

LET heapify(v, k, i, last) BE

{ LET j = i+i // If there is a son (or two), j = subscript of first.

AND x = k // x will hold the larger of the sons if any.

IF j<=last DO x := v!j // j, x = subscript and key of first son.

IF j< last DO

{ LET y = v!(j+1) // y = key of the other son.

IF x<y DO x,j := y, j+1 // j, x = subscript and key of larger son.

}

IF k>=x DO

{ v!i := k // k is not lower than larger son if any.

RETURN

}

v!i := x

i := j

} REPEAT

AND heapsort(v, upb) BE

{ FOR i = upb/2 TO 1 BY -1 DO heapify(v, v!i, i, upb)

FOR i = upb TO 2 BY -1 DO

{ LET k = v!i

v!i := v!1

heapify(v, k, 1, i-1)

}

}

LET start() = VALOF {

LET v = VEC 1000)

FOR i = 1 TO 1000 DO v!i := randno(1_000_000)

heapsort(v, 1000)

FOR i = 1 TO 1000 DO

{ IF i MOD 10 = 0 DO newline()

writef(" %i6", v!i)

}

newline()

}

</lang>