Algorithm 232: Heapsort

Abstract

a,b,j,k,s,d,n,p); value n; real a,b; integer array s,d; integer j,k,n,p; comment a procedure using Jensen's device which exchanges rows or columns of a matrix to achieve a rearrangement specified by the permutation vectors s,d[l :n].Elements of s specify the original source locations while elements of d specify the desired destination locations.Normally a and b will be called as subscripted variables of the same array.The parameters j,k nominate the subscripts of the dimension affected by the permutation, pis the Jensen parameter.As an example of the use of this procedure, suppose r,c[l :n] to contain the row and column subscripts of the successive matrix pivots used in a matrix inversion of an array a[l :n,l :n]; i.e. r[l], c[l] are the relative subscripts of the first pivot r[2], c(2] those of the second pivot and so on.The two calls matrixperm (a[j,p], a[k,p], j,k,r,c,n,p) and matrixperm (a[p,j], a[p,k], j,k,c,r,n,p) will perform the required rearrangement of rows and columns respectively; begin integer array tag, loc[l :n]; integer i,t; real w; comment set up initial vector tag number and address arrays;for i := 1 step 1 until n do tag[i] := loc[i] := i; • comment start permutation;for i := 1 step 1 until