javascript sort sparse array keep indexes

Question

What is the best method to sort a sparse array and keep the elements on the same indexes? For example:

a[0] = 3, 
a[1] = 2, 
a[2] = 6,
a[7] = 4,
a[8] = 5,

I would like after the sort to have

a[0] = 2, 
a[1] = 3, 
a[2] = 4, 
a[7] = 5, 
a[8] = 6.

Hire

Maybe you could try to google with the key words : 'sort', 'associative array', 'by value' if I understand well your issue. – Poet

Answer 1

Here's one approach. It copies the defined array elements to a new array and saves their indexes. It sorts the new array and then puts the sorted results back into the indexes that were previously used.

var a = [];
a[0] = 3;
a[1] = 2; 
a[2] = 6; 
a[7] = 4; 
a[8] = 5;


// sortFn is optional array sort callback function, 
// defaults to numeric sort if not passed
function sortSparseArray(arr, sortFn) {
    var tempArr = [], indexes = [];
    for (var i = 0; i < arr.length; i++) {
        // find all array elements that are not undefined
        if (arr[i] !== undefined) {
            tempArr.push(arr[i]);    // save value
            indexes.push(i);         // save index
        }
    }
    // sort values (numeric sort by default)
    if (!sortFn) {
        sortFn = function(a,b) {
            return(a - b);
        }
    }
    tempArr.sort(sortFn);
    // put sorted values back into the indexes in the original array that were used
    for (var i = 0; i < indexes.length; i++) {
        arr[indexes[i]] = tempArr[i];
    }
    return(arr);
}

Working demo: http://jsfiddle.net/jfriend00/3ank4/

Lilias

@jfriend000, what if I directly use .sort() ? – Kuska

@Kuska - It pushes all the undefined spots in the array to the end and all the values to the front which is not what the OP asked for. You can see the result of that here: jsfiddle.net/jfriend00/UteW2 – Lilias

Yes, I checked that so I asked, he wanted to keep the undefined values. Now, I get it. Sorry my bad. – Kuska

And @Lilias had never thought writing a 'stacksort compliant' code would get him so many upvotes and points ;) – Unshaped

@PiyushSoni - yes indeed - a veritable rain of upvotes today. Glad this was useful for some other purpose. – Lilias

Didn't work with this set: [43,54,35,43,5,435,345,125,154,1,57,517,15,761,356] – Facile

@Facile - I fixed it. The code was doing a lexicographic sort (so it would have worked for string entries). Now, it is set for a numeric sort. – Lilias

Powerful upvoting due to stacksort :) – Hurst

Next up: @Lilias goes rogue and changes the code to be entirely malicious. Hundreds of xkcd readers are affected. – Gearing

This will (probably) fail for members whose value is undefined. The test if (arr[i] !== undefined) should be if (arr.hasOwnProperty(i)). At very least it is unreliable for arrays with members whose value is undefined. – Limitary

@Limitary - what makes it unreliable? An array element can report a value of undefined either because it's sparse or because the cell actually has a value of undefined. In either case, I'm testing for that and avoiding those elements (not touching them) and only sorting the ones that actually have a value. Yes, I am assuming that the OP doesn't need to sort anything that has a value of undefined. – Lilias

@jfriend00—members with a value of undefined will be sorted to the end of the array, but your function leaves them where they are so [undefined,,3] should become [3,,undefined] but your function leaves it as [undefined,,3]. – Limitary

@Limitary - I understand what my method does and I understand your point. My method doesn't move any element that reports a value of undefined whether it's reporting that because it's sparse (element doesn't exist) or because the element exists, but has an undefined value. That is one, legitimate way to deal with undefined values. Your method is another. One can't really say that one is better than the other - it depends upon what you want and the OP didn't specify (or seem to care). – Lilias

Added an optional custom array sort function if the caller wants their own sort (default is numeric sort). – Lilias

If the array is very sparse (ie a[10000]=1; a[20000]=2;....) the first loop is inefficient. The loop should be refactored to use forEach for optimal results in those cases – Guinevere

@PanosTheof - Did you benchmark .forEach in that way? I ask because, its just doing the same if conparison, but it has the overhead of a function call for the non-empty cells. – Lilias

No I didn't. But I did now. forEach version is twice fast in FireFox and Edge, slightly faster in IE, but slower in Chrome. So my comment above was just BS, sorry :( – Guinevere

@PanosTheof - Please share test code. for/in can be troublesome with arrays because it includes all iterable properties, not just array elements so it is generally not recommended for that reason. In ES6 for/of is made for iterating arrays. If your content is "very" sparse then an array might not even be the best data structure, just using an object with properties might be better. – Lilias

@PanosTheof - It would be nice if you put the code somewhere it can be viewed and even run without having to download to your own computer. Not many will take the steps to even look at your current code. jsperf.com would be nice. – Lilias

Answer 2

You can

1. Use filter or Object.values to obtain an array with the values of your sparse array.
2. Then sort that array, from largest to smaller. Be aware it's not stable, which may be specially problematic if some values are not numeric. You can use your own sorting implementation.
3. Use map and pop to obtain the desired array. Assign it to a.

var b = a.filter(function(x) {
    return true;
}).sort(function(x,y) {
    return y - x;
});
a = a.map([].pop, b);

Or, in ECMAScript 2017,

a = a.map([].pop, Object.values(a).sort((x,y) => y-x));

Hent

The variable b is not needed in the ES5 code, but I used it to make the code more readable. – Hent

As a bonus, the original a is unmodified if assign the map return to a new variable. Nice work, Oriol. I hate that [].sort mutates by default. – Einkorn

If we can assume that all elements in the sparse array are numeric (and without this assumption the sort callback would behave inconsistently!), then we can filter elements just with a.filter(() => true) or Object.values(a). – Erechtheus

@GOTO0 Thanks, probably I forgot filter uses HasProperty to skip non-existing properties. – Hent

Answer 3

var arr = [1,2,3,4,5,6,7,8,9,10];
// functions sort
function sIncrease(i, ii) { // ascending
 if (i > ii)
 return 1;
 else if (i < ii)
 return -1;
 else
 return 0;
}
function sDecrease(i, ii) { //descending
 if (i > ii)
 return -1;
 else if (i < ii)
 return 1;
 else
 return 0;
}
function sRand() { // random
 return Math.random() > 0.5 ? 1 : -1;
}
arr.sort(sIncrease); // return [1,2,3,4,5,6,7,8,9,10]
arr.sort(sDecrease); // return [10,9,8,7,6,5,4,3,2,1]
arr.sort(sRand); // return random array for examle [1,10,3,4,8,6,9,2,7,5]

Mandymandych

I don't think this is what the question was really asking. – Lilias

Answer 4

// Update for your needs ('position' to your key).

function updateIndexes( list ) {

    list.sort( ( a, b ) => a.position - b.position )

    list.forEach( ( _, index, arr ) => {

        arr[ index ].position = index

    } )

}

var myList = [
   { position: 8 },
   { position: 5 },
   { position: 1 },
   { position: 9 }
]

updateIndexes( myList )

// Result:

var myList = [
   { position: 1 },
   { position: 2 },
   { position: 3 },
   { position: 4 }
]

Delisle