find/trace element in a sorted array

Question

Let's say there is an array like var arr = [{id:'anId', value: 'aValue'}, ......] and a custom sorting by value is done to it:

arr.sort(function(){
   // sorting.....
});

Is there a way to trace an element during sorting?

If not is there an efficient search implementation of finding it by id without iterating and checking on each item?

Appreciate your kind help.

unless you have the array sorted by id, no way of finding by id without iterating all. If you do have them sorted, a binary search approach would work, but doubt you need it to be that efficient, is your data big? — juvian
– juvian, Commented Jan 19, 2015 at 18:24
It might get big, yes. Unfortunately I need the order by value property because I'm more interested in the position than the element itself or a simple map with id keys would help in the first place. — kidwon
– kidwon, Commented Jan 19, 2015 at 18:28
What do you mean by "trace"? Do you know where the element is before sorting, and want to keep track of where it ended up after sorting? Or do you want to look for the element (not yet knowing where it is) at the same time as you're sorting the array? — Edward
– Edward, Commented Jan 19, 2015 at 18:30

juvian · Accepted Answer · 2015-01-20 18:34:34Z

2

Since you are already applying a sorting method, which will iterate through all the elements, you can get the best performance by checking for your target ID during the sort iterations:

var prevPos = // here goes the current index of the object in the array
var item;
arr.sort(function(a,b){
    if(a.id == 'mySearchID'){
        console.log('found it, better store it')
        item = a;
        f(a.value < b.value) prevPos++ // item moved, change current pos
    }else if(b.id == 'mySearchID'){
         console.log('found it, better store it')
         item = b;
         if(a.value < b.value) prevPos-- // item moved, change current pos
    }
    //your sorting method
    return a.value < b.value
}); 
console.log(item, prevPos) //gets item obj and its new position in the array

Note that item may be updated multiple times depending on how many times your desired object is moved during the sort, but by the end of the sort item will be a reference to your object in the sorted array.

edited Jan 20, 2015 at 18:34

answered Jan 19, 2015 at 18:42

juvian

16.1k2 gold badges42 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

kidwon Over a year ago

This good but I am interested in its position in the array not the object itself, because I know it before sorting and I can get it but it is the order I'm interested in. I wasn't very clear about that. Thank you for the kind help, appreciate it +1.

juvian Over a year ago

@kidwon Well, you can then just do arr.indexOf(item) to get new position. If you want to do it more efficently, you could do something like this: jsfiddle.net/juvian/jef4z96o

kidwon Over a year ago

I doubt that is reliable because one can't determine which elements are compared against each other, the elements are not shifted with 1. The shift step might be across 7 items for example. So prevPos represents the overall shifting progress ascending or descending during the sort. jsfiddle.net/jef4z96o/1 but not the current position of the element.

kidwon Over a year ago

But indexOf is working I thought it works on primitive values only , 10x. You should put that in your answer, i will accept it.

kidwon Over a year ago

Although in js it isn't faster than a for loop so no progress here.

|

Collectives™ on Stack Overflow

find/trace element in a sorted array

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related