dsortins

Sort a double-precision floating-point strided array using insertion sort.

Usage

var dsortins = require( '@stdlib/blas/ext/base/dsortins' );

dsortins( N, order, x, stride )

Sorts a double-precision floating-point strided array x using insertion sort.

var Float64Array = require( '@stdlib/array/float64' );

var x = new Float64Array( [ 1.0, -2.0, 3.0, -4.0 ] );

dsortins( x.length, 1.0, x, 1 );
// x => <Float64Array>[ -4.0, -2.0, 1.0, 3.0 ]

The function has the following parameters:

  • N: number of indexed elements.
  • order: sort order. If order < 0.0, the input strided array is sorted in decreasing order. If order > 0.0, the input strided array is sorted in increasing order. If order == 0.0, the input strided array is left unchanged.
  • x: input Float64Array.
  • stride: index increment.

The N and stride parameters determine which elements in x are accessed at runtime. For example, to sort every other element

var Float64Array = require( '@stdlib/array/float64' );
var floor = require( '@stdlib/math/base/special/floor' );

var x = new Float64Array( [ 1.0, -2.0, 3.0, -4.0 ] );
var N = floor( x.length / 2 );

dsortins( N, -1.0, x, 2 );
// x => <Float64Array>[ 3.0, -2.0, 1.0, -4.0 ]

Note that indexing is relative to the first index. To introduce an offset, use typed array views.

var Float64Array = require( '@stdlib/array/float64' );
var floor = require( '@stdlib/math/base/special/floor' );

// Initial array...
var x0 = new Float64Array( [ 1.0, 2.0, 3.0, 4.0 ] );

// Create an offset view...
var x1 = new Float64Array( x0.buffer, x0.BYTES_PER_ELEMENT*1 ); // start at 2nd element
var N = floor( x0.length/2 );

// Sort every other element...
dsortins( N, -1.0, x1, 2 );
// x0 => <Float64Array>[ 1.0, 4.0, 3.0, 2.0 ]

dsortins.ndarray( N, order, x, stride, offset )

Sorts a double-precision floating-point strided array x using insertion sort and alternative indexing semantics.

var Float64Array = require( '@stdlib/array/float64' );

var x = new Float64Array( [ 1.0, -2.0, 3.0, -4.0 ] );

dsortins.ndarray( x.length, 1.0, x, 1, 0 );
// x => <Float64Array>[ -4.0, -2.0, 1.0, 3.0 ]

The function has the following additional parameters:

  • offset: 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 Float64Array = require( '@stdlib/array/float64' );

var x = new Float64Array( [ 1.0, -2.0, 3.0, -4.0, 5.0, -6.0 ] );

dsortins.ndarray( 3, 1.0, x, 1, x.length-3 );
// x => <Float64Array>[ 1.0, -2.0, 3.0, -6.0, -4.0, 5.0 ]

Notes

  • If N <= 0 or order == 0.0, both functions return x 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 worst case time complexity O(N^2).
  • The algorithm is efficient for small strided arrays (typically N <= 20) and is particularly efficient for sorting strided arrays which are already substantially sorted.
  • The algorithm is stable, meaning that the algorithm does not change the order of strided array elements which are equal or equivalent (e.g., NaN values).
  • The input strided array is sorted in-place (i.e., the input strided array is mutated).

Examples

var round = require( '@stdlib/math/base/special/round' );
var randu = require( '@stdlib/random/base/randu' );
var Float64Array = require( '@stdlib/array/float64' );
var dsortins = require( '@stdlib/blas/ext/base/dsortins' );

var rand;
var sign;
var x;
var i;

x = new Float64Array( 10 );
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;
}
console.log( x );

dsortins( x.length, -1.0, x, -1 );
console.log( x );
Did you find this page helpful?