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.
-
Maybe you could try to google with the key words : 'sort', 'associative array', 'by value' if I understand well your issue.Ricola3D– Ricola3D2012-08-27 07:24:05 +00:00Commented Aug 27, 2012 at 7:24
Add a comment
|
4 Answers
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/
19 Comments
Jashwant
@jfriend000, what if I directly use
.sort() ?
Piyush Soni
And @jfriend00 had never thought writing a 'stacksort compliant' code would get him so many upvotes and points ;)
jfriend00
@OrhanC1 - 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.
Stilgar
Powerful upvoting due to stacksort :)
nzifnab
Next up: @jfriend00 goes rogue and changes the code to be entirely malicious. Hundreds of xkcd readers are affected.
|
You can
- Use
filterorObject.valuesto obtain an array with the values of your sparse array. - Then
sortthat 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. - Use
mapandpopto obtain the desired array. Assign it toa.
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));
4 Comments
Oriol
The variable
b is not needed in the ES5 code, but I used it to make the code more readable.
Mulan
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.
GOTO 0
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).Oriol
@GOTO0 Thanks, probably I forgot
filter uses HasProperty to skip non-existing properties.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]
1 Comment
jfriend00
I don't think this is what the question was really asking.
// 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 }
]
