CODEWITHSUNDEEP
javascriptarrays
cronoklee
cronoklee

Reputation: 6712

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

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.

Upvotes: 9

Views: 9820

Answers (7)

woojoo666
woojoo666

Reputation: 7921

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

Upvotes: 9

Marino Šimić
Marino Šimić

Reputation: 7342

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

Upvotes: 1

kennebec
kennebec

Reputation: 104770

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
*/

Upvotes: 0

alex
alex

Reputation: 490233

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.

Upvotes: 12

jordancpaul
jordancpaul

Reputation: 2964

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

Upvotes: 0

Elian Ebbing
Elian Ebbing

Reputation: 19027

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

Upvotes: 4

Dutchie432
Dutchie432

Reputation: 29160

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;

Upvotes: -1

Related Questions