sort2ins.js (2270B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2021 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 'use strict'; 20 21 // MAIN // 22 23 /** 24 * Simultaneously sorts two arrays based on the sort order of the first array using insertion sort. 25 * 26 * ## Notes 27 * 28 * - The first array is sorted in increasing order according to absolute value. 29 * - The algorithm has space complexity `O(1)` and worst case time complexity `O(N^2)`. 30 * - The algorithm is efficient for small arrays (typically `N <= 20``) and is particularly efficient for sorting arrays which are already substantially sorted. 31 * - The algorithm is **stable**, meaning that the algorithm does **not** change the order of array elements which are equal or equivalent. 32 * - The input arrays are sorted in-place (i.e., the input arrays are mutated). 33 * 34 * @private 35 * @param {Array} x - first array 36 * @param {Array} y - second array 37 * @returns {void} 38 * 39 * @example 40 * var x = [ -4, -2, 3, 1 ]; 41 * var y = [ 0, 1, 2, 3 ]; 42 * 43 * sort2ins( x, y ); 44 * 45 * console.log( x ); 46 * // => [ 1, -2, 3, -4 ] 47 * 48 * console.log( y ); 49 * // => [ 3, 1, 2, 0 ] 50 */ 51 function sort2ins( x, y ) { 52 var avx; 53 var aux; 54 var ix; 55 var iy; 56 var jx; 57 var jy; 58 var vx; 59 var vy; 60 var ux; 61 var i; 62 63 ix = 1; 64 iy = 1; 65 66 // Sort in increasing order... 67 for ( i = 1; i < x.length; i++ ) { 68 vx = x[ ix ]; 69 avx = ( vx < 0 ) ? -vx : vx; 70 71 vy = y[ iy ]; 72 73 jx = ix - 1; 74 jy = iy - 1; 75 76 // Shift all larger values to the left of the current element to the right... 77 while ( jx >= 0 ) { 78 ux = x[ jx ]; 79 aux = ( ux < 0 ) ? -ux : ux; 80 if ( aux <= avx ) { 81 break; 82 } 83 x[ jx+1 ] = ux; 84 y[ jy+1 ] = y[ jy ]; 85 jx -= 1; 86 jy -= 1; 87 } 88 x[ jx+1 ] = vx; 89 y[ jy+1 ] = vy; 90 ix += 1; 91 iy += 1; 92 } 93 } 94 95 96 // EXPORTS // 97 98 module.exports = sort2ins;