Quickest way to sort a JS array based on another array's values?

Question

There's some similar posts knocking about but I cant find anything that quite addresses this particular issue... I have two arrays of paired 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's the most processor friendly way to sort the arrays so that array A is in numerical ascending order and the data structure is maintained? I guess built in array.sort(function) would be quickest but I'm not confident of the syntax.

Answer 1

Kind of hacky, 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 a.A - b.A;
});

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.

Output

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

Basically, we are making objects with a clear tie between A and B within a new array, and then sort()ing that.

Then I go back and rebuild the original the two arrays.

Update

Már Örlygsson makes a good point in the comments. Instead of producing an object like {A: 0.5, B: 'a'}, he suggests placing the A an B values in arrays like [0.5, 'a'].

This should be faster, though it will be slightly less readable if needing to debug the all array. I'll leave this up to you, if you are experiencing performance issues, profile both these methods and choose the fastest.

Answer 2

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

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's the jsfiddle

EDIT: semi-one-liner inspired by chowey's 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 build-in Array.sort().

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

After this you can just write:

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

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);
    }
}

array is for numbers, array2 is for strings, they must be of same length.

this is quicksort so time is O(N LogN)

source is literateprograms.org, license is MIT, modification to manage the second array made by me

Answer 5

With any sorting algorithm, there is a tradeoff between algorithm time, and other constraints (usually memory). You might want to take a look at Quicksort and Bubble Sort, two common and very fast sorting algorithms. You would need to make minor modifications, since you are actually sorting two array's with the first being the source of the data to sort - but this sort of change is trivial.

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

Answer 6

Putting the two arrays together before the sort is the simplest 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, if possible, actually making a data structure. This way you can sort $A[] based on one property while maintaining the structure. I havent done any speed tests or anything, 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;