ssort2hp
Simultaneously sort two single-precision floating-point strided arrays based on the sort order of the first array using heapsort.
Usage
var ssort2hp = require( '@stdlib/blas/ext/base/ssort2hp' );
ssort2hp( N, order, x, strideX, y, strideY )
Simultaneously sorts two single-precision floating-point strided arrays based on the sort order of the first array x
using heapsort.
var Float32Array = require( '@stdlib/array/float32' );
var x = new Float32Array( [ 1.0, -2.0, 3.0, -4.0 ] );
var y = new Float32Array( [ 0.0, 1.0, 2.0, 3.0 ] );
ssort2hp( x.length, 1.0, x, 1, y, 1 );
console.log( x );
// => <Float32Array>[ -4.0, -2.0, 1.0, 3.0 ]
console.log( y );
// => <Float32Array>[ 3.0, 1.0, 0.0, 2.0 ]
The function has the following parameters:
- N: number of indexed elements.
- order: sort order. If
order < 0.0
, the input strided arrayx
is sorted in decreasing order. Iforder > 0.0
, the input strided arrayx
is sorted in increasing order. Iforder == 0.0
, the input strided arrays are left unchanged. - x: first input
Float32Array
. - strideX:
x
index increment. - y: second input
Float32Array
. - strideY:
y
index increment.
The N
and stride
parameters determine which elements in x
and y
are accessed at runtime. For example, to sort every other element
var Float32Array = require( '@stdlib/array/float32' );
var floor = require( '@stdlib/math/base/special/floor' );
var x = new Float32Array( [ 1.0, -2.0, 3.0, -4.0 ] );
var y = new Float32Array( [ 0.0, 1.0, 2.0, 3.0 ] );
var N = floor( x.length / 2 );
ssort2hp( N, -1.0, x, 2, y, 2 );
console.log( x );
// => <Float32Array>[ 3.0, -2.0, 1.0, -4.0 ]
console.log( y );
// => <Float32Array>[ 2.0, 1.0, 0.0, 3.0 ]
Note that indexing is relative to the first index. To introduce an offset, use typed array
views.
var Float32Array = require( '@stdlib/array/float32' );
var floor = require( '@stdlib/math/base/special/floor' );
// Initial arrays...
var x0 = new Float32Array( [ 1.0, 2.0, 3.0, 4.0 ] );
var y0 = new Float32Array( [ 0.0, 1.0, 2.0, 3.0 ] );
// Create offset views...
var x1 = new Float32Array( x0.buffer, x0.BYTES_PER_ELEMENT*1 ); // start at 2nd element
var y1 = new Float32Array( y0.buffer, y0.BYTES_PER_ELEMENT*1 ); // start at 2nd element
var N = floor( x0.length/2 );
// Sort every other element...
ssort2hp( N, -1.0, x1, 2, y1, 2 );
console.log( x0 );
// => <Float32Array>[ 1.0, 4.0, 3.0, 2.0 ]
console.log( y0 );
// => <Float32Array>[ 0.0, 3.0, 2.0, 1.0 ]
ssort2hp.ndarray( N, order, x, strideX, offsetX, y, strideY, offsetY )
Simultaneously sorts two single-precision floating-point strided arrays based on the sort order of the first array x
using heapsort and alternative indexing semantics.
var Float32Array = require( '@stdlib/array/float32' );
var x = new Float32Array( [ 1.0, -2.0, 3.0, -4.0 ] );
var y = new Float32Array( [ 0.0, 1.0, 2.0, 3.0 ] );
ssort2hp.ndarray( x.length, 1.0, x, 1, 0, y, 1, 0 );
console.log( x );
// => <Float32Array>[ -4.0, -2.0, 1.0, 3.0 ]
console.log( y );
// => <Float32Array>[ 3.0, 1.0, 0.0, 2.0 ]
The function has the following additional parameters:
- offsetX:
x
starting index. - offsetY:
y
starting index.
While typed array
views mandate a view offset based on the underlying buffer
, the offset
parameter supports indexing semantics based on a starting index. For example, to access only the last three elements of x
var Float32Array = require( '@stdlib/array/float32' );
var x = new Float32Array( [ 1.0, -2.0, 3.0, -4.0, 5.0, -6.0 ] );
var y = new Float32Array( [ 0.0, 1.0, 2.0, 3.0, 4.0, 5.0 ] );
ssort2hp.ndarray( 3, 1.0, x, 1, x.length-3, y, 1, y.length-3 );
console.log( x );
// => <Float32Array>[ 1.0, -2.0, 3.0, -6.0, -4.0, 5.0 ]
console.log( y );
// => <Float32Array>[ 0.0, 1.0, 2.0, 5.0, 3.0, 4.0 ]
Notes
- If
N <= 0
ororder == 0.0
, both functions leavex
andy
unchanged. - The algorithm distinguishes between
-0
and+0
. When sorted in increasing order,-0
is sorted before+0
. When sorted in decreasing order,-0
is sorted after+0
. - The algorithm sorts
NaN
values to the end. When sorted in increasing order,NaN
values are sorted last. When sorted in decreasing order,NaN
values are sorted first. - The algorithm has space complexity
O(1)
and time complexityO(N log2 N)
. - The algorithm is unstable, meaning that the algorithm may change the order of strided array elements which are equal or equivalent (e.g.,
NaN
values). - The input strided arrays are sorted in-place (i.e., the input strided arrays are mutated).
Examples
var round = require( '@stdlib/math/base/special/round' );
var randu = require( '@stdlib/random/base/randu' );
var Float32Array = require( '@stdlib/array/float32' );
var ssort2hp = require( '@stdlib/blas/ext/base/ssort2hp' );
var rand;
var sign;
var x;
var y;
var i;
x = new Float32Array( 10 );
y = new Float32Array( 10 ); // index array
for ( i = 0; i < x.length; i++ ) {
rand = round( randu()*100.0 );
sign = randu();
if ( sign < 0.5 ) {
sign = -1.0;
} else {
sign = 1.0;
}
x[ i ] = sign * rand;
y[ i ] = i;
}
console.log( x );
console.log( y );
ssort2hp( x.length, -1.0, x, -1, y, -1 );
console.log( x );
console.log( y );
References
- Williams, John William Joseph. 1964. "Algorithm 232: Heapsort." Communications of the ACM 7 (6). New York, NY, USA: Association for Computing Machinery: 347–49. doi:10.1145/512274.512284.
- Floyd, Robert W. 1964. "Algorithm 245: Treesort." Communications of the ACM 7 (12). New York, NY, USA: Association for Computing Machinery: 701. doi:10.1145/355588.365103.