Fastest way to sort a JS array based on other array values?

Question

There are similar entries there, but I can not find anything that completely solves this problem ... I have two arrays of pair values:

var A=[0.5, 0.6, 0.5, 0.7, 0.8, 0.1] var B=['a','b','c','d','e','f'] //note: a=0.5, b=0.6, c=0.5, d=0.7, etc 

What is the most convenient way for the processor to sort arrays, so that array A is numerically in increasing order and the data structure is supported? I think that the built-in array array.sort (function) would be the fastest, but I'm not sure about the syntax.

Answer 1

Kind of hacks, but it works.

 var A = [0.5, 0.6, 0.5, 0.7, 0.8, 0.1]; var B = ['a', 'b', 'c', 'd', 'e', 'f']; var all = []; for (var i = 0; i < B.length; i++) { all.push({ 'A': A[i], 'B': B[i] }); } all.sort(function(a, b) { return aA - bA; }); A = []; B = []; for (var i = 0; i < all.length; i++) { A.push(all[i].A); B.push(all[i].B); } console.log(A, B); 

jsFiddle .

Exit

 0.1, 0.5, 0.5, 0.6, 0.7, 0.8 ["f", "a", "c", "b", "d", "e"] 

Basically, we create objects with a clear relationship between A and B in a new array, and then sort() ing.

Then I go back and restore the original of two arrays.

Update

Már Örlygsson gives a good conclusion in the comments. Instead of creating an object such as {A: 0.5, B: 'a'} , he suggests putting the values ​​of A an B into arrays of the type [0.5, 'a'] .

This should be faster, although it will be slightly less readable if you need to debug the all array. I will leave this to you if you encounter performance problems, go through both of these methods and select the fastest.

Answer 2

I noticed that all of the above solutions used the map. Another method that saves a bit of memory is to create an array of indexes, sort the indexes based on A, and then restore A and B based on the indexes.

 var A=[0.5, 0.6, 0.5, 0.7, 0.8, 0.1]; var B=['a','b','c','d','e','f']; var indices = A.map(function(elem, index){return index;}); //an array of indices indices.sort(function (a,b) {return A[a] - A[b];}); //print out the results for (var i = 0; i < A.length; i++) document.body.innerHTML += 'A: ' + A[indices[i]] + ', B: ' + B[indices[i]] + '<br>'; 

here jsfiddle

EDIT: semi-single-line, inspired by chowey comment :

 var BSorted = A.map(function(e,i){return i;}) .sort(function(a,b){return A[a] - A[b];}) .map(function(e){return B[e];}); 

Answer 3

It would be much simpler if you had one array with tuples instead of two arrays. Because then you can use the built-in Array.sort() .

 var arr = [{a: 0.5, b: 'a'}, {a: 0.6, b: 'b'}, {a: 0.5, b: 'c'}, ... ]; 

After that, you can simply write:

 arr.sort(function(x,y) { return xa - ya }); 

Answer 4

 Array.prototype.swap=function(a, b) { var tmp=this[a]; this[a]=this[b]; this[b]=tmp; } function partition(array, array2, begin, end, pivot) { var piv=array[pivot]; array.swap(pivot, end-1); array2.swap(pivot, end-1); var store=begin; var ix; for(ix=begin; ix<end-1; ++ix) { if(array[ix]<=piv) { array.swap(store, ix); array2.swap(store, ix); ++store; } } array.swap(end-1, store); array2.swap(end-1, store); return store; } function qsort(array, array2, begin, end) { if(end-1>begin) { var pivot=begin+Math.floor(Math.random()*(end-begin)); pivot=partition(array, array2, begin, end, pivot); qsort(array, array2, begin, pivot); qsort(array, array2, pivot+1, end); } } 

an array for numbers, array2 for strings, they must be the same length.

this is quicksort so the time is O (n logn)

source - literateprograms.org, license - MIT, modification for managing the second array made by me

Answer 5

With any sorting algorithm, there is a trade-off between algorithm time and other constraints (usually memory). You can take a look at Quicksort and Bubble Sort , two simple and very fast sorting algorithms. You will need to make minor changes, since you are actually sorting two arrays with the first being the data source for sorting, but such a change is trivial.

EDIT: Note: array.sort () will not work for you, since you want changes to arr1 to be reflected in arr2. You must write your own sort function.

Answer 6

Combining two arrays before sorting is the easiest way.

 var a1, b1, A= [0.5, 0.6, 0.5, 0.7, 0.8, 0.1], B= ['a', 'b', 'c', 'd', 'e', 'f'], ab= A.map(function(itm, i){ return [itm, i]; }); ab.sort(function(a, b){ return a[0]-b[0]; }); B= ab.map(function(itm){ A.push(itm[0]); return B[itm[1]]; }); A= A.splice(B.length); alert(A+'\n'+B) /* returned value: (String) 0.1, 0.5, 0.5, 0.6, 0.7, 0.8 f, a, c, b, d, e */ 

Answer 7

You might be better off creating a data structure if possible. This way you can sort $A[] based on a single property while maintaining the structure. I have not done any speed tests or anything else, but maybe something like ...

 A[0]['label']='a'; A[0]['value']=0.5; A[1]['label']='b'; A[1]['value']=0.6; A[2]['label']='c'; A[2]['value']=0.5; A[3]['label']='d'; A[3]['value']=0.7; A[4]['label']='e'; A[4]['value']=0.8; A[5]['label']='f'; A[5]['value']=0.1;