Sorting an array of arrays...
Daniel
This is my first visit here, and thus my first post ;)
I'm trying to make a backend, and want to use Javascript to sort an array
containing information about persons, each person has an associative array
holding the data, like id, firstname, lastname, etc.
The data is presented in an <option> list, and I'd like the user to be able
to change the sorting order, like "Sort by last name", "Sort by first name",
and so. I understand the built-in Javascript sort function, but I'm kinda
lost of how I would go around sorting each person's array inside the "head
array" like this.
Any links or examples?
Thanks in advance,
Daniel, Denmark
Martin Honnen
You can sort an array of any kind by passing in an appropriate
comparison function e.g.
function Person (prename, surname) {
this.prename = prename;
this.surname = surname;
}
Person.prototype.toString = function () {
return this.prename + " " + this.surname;
}
var riders = [
new Person("Lance", "Armstrong"),
new Person("Jan", "Ullrich"),
new Person("Erik", "Zabel"),
new Person("Mario", "Cippolini")
]
function sortSurname (p1, p2) {
if (p1.surname < p2.surname)
return -1;
else if (p1.surname > p2.surname)
return 1;
else if (p1.prename < p1.prename)
return -1;
else
return 1;
}
function sortPrename (p1, p2) {
if (p1.prename < p2.prename)
return -1;
else if (p1.prename > p2.prename)
return 1;
else if (p1.surname < p2.surname)
return -1;
else
return 1;
}
alert(riders)
riders.sort(sortSurname);
alert(riders)
riders.sort(sortPrename);
alert(riders)
--
Martin Honnen
http://javascript.faqts.com/
Lasse Reichstein Nielsen
> This is my first visit here, and thus my first post ;)
Welcome :)
> I'm trying to make a backend, and want to use Javascript to sort an array
> containing information about persons, each person has an associative array
> holding the data, like id, firstname, lastname, etc.
That "associate array" don't have to be an Array, it can just be an Object.
It is only if you use indexing by number (foo[2]) that you gain any benefit
from using an Array.
So, you have an Array of Objects.
> The data is presented in an <option> list, and I'd like the user to be able
> to change the sorting order, like "Sort by last name", "Sort by first name",
> and so. I understand the built-in Javascript sort function, but I'm kinda
> lost of how I would go around sorting each person's array inside the "head
> array" like this.
You don't want to sort the object, you just want to sort the array of
objects by different criteria.
You can use the standard sort function on arrays for that, you just have
to give it different comparison functions.
> Any links or examples?
Make a comparison function (I don't *think* there is one built in, sadly,
but please correct me if I am wrong!)
function cmp(a,b) {
return (a<b)?-1:(a>b)?1:0;
}
Then you can easily sort the array for different properties of the objects:
First name:
myArray.sort(function(a,b){return cmp(a.firstname,b.firstname);});
Last name:
myArray.sort(function(a,b){return cmp(a.lastname,b.lastname);});
Id:
myArray.sort(function(a,b){return cmp(a.id,b.id);});
Then you'll just have to map that to your option list.
/L
--
Lasse Reichstein Nielsen - l...@hotpop.com
Art D'HTML: <URL:http://www.infimum.dk/HTML/randomArtSplit.html>
'Faith without judgement merely degrades the spirit divine.'
Daniel
At first I didn't quite get your code, seeing as it uses an array of objects
instead of my array of arrays, but then I found some litterature on the
optional [function] in .sort([function]). And now I get it =) I'm gonna try
it out with my arrays-array and see how efficient it is, and I'll probably
run into loads of other problems and screaming for help ;)
Thanks again,
Daniel =)
--
There are 10 kinds of people: Those who know binary and those who don't.
"Martin Honnen" <Martin...@t-online.de> wrote in message
news:3EDF26D4...@t-online.de...
Daniel
Thanks for your reply! I'm afraid, though, that you've lost me on several
occasions... I'm quite the newbie in this Javascript thingamajig =)
> function cmp(a,b) {
> return (a<b)?-1:(a>b)?1:0;
> }
Okay, I just found out how to use these sort functions, so I know what this
is, but what's that ? and : stuff? I'm assuming it's short (and probably
faster) for something else, but I'm not sure what...
> First name:
> myArray.sort(function(a,b){return cmp(a.firstname,b.firstname);});
>
> Last name:
> myArray.sort(function(a,b){return cmp(a.lastname,b.lastname);});
>
> Id:
> myArray.sort(function(a,b){return cmp(a.id,b.id);});
Could you please explain this? Especially the inclusion of (a,b), and the
{return ...} part... As I understood, the a and b shouldn't be put in the
argument, only "myArray.sort(mySortFunction)"-style? I'm guessing that your
method is the cool and fast power-user approach, so I REALLY want to
understand it ;)
Also, if I'd like to stay with the arrays-in-an-array approach, could I just
use a["lastname"] instead of a.lastname? Are there any advantages to the
object approach over the array approach?
Sorry if I'm terribly much a newbie here!
Thank you very much =)
Daniel
--
There are 10 kinds of people: Those who know binary and those who don't.
"Lasse Reichstein Nielsen" <l...@hotpop.com> wrote in message
news:fzmolo...@hotpop.com...
Lasse Reichstein Nielsen
> > function cmp(a,b) {
> > return (a<b)?-1:(a>b)?1:0;
> > }
>
> Okay, I just found out how to use these sort functions, so I know what this
> is, but what's that ? and : stuff? I'm assuming it's short (and probably
> faster) for something else, but I'm not sure what...
It is an "expression conditional" with a notation that was originally
used in C, and is now in all the languages with derivative syntax
(C++, Java, C#, Perl, ... and javascript).
The traditional "statement conditional" is the if expression.
if (expression)
statement1;
else
statement2;
It is itself a statement, and depending on the value of an expression,
it is equivalent to one of two statements.
The expression conditional, ?:, works the same for expressions.
expression1 ? expression2 : expression3
can be read as
if (expression1) then become (expression2) else become (expression3)
It is itself an expression, and depending on the value of the first
expression, it is equivalent to one of the two other expressions.
So instead of writing, e.g.,
var x;
if (condition) {
x = expression1;
} else {
x = expression2;
}
you can avoid the duplicate "x =" and just write
var x = condition?expression1:expression2;
It is shorter. I don't know if it is more efficient.
> > First name:
> > myArray.sort(function(a,b){return cmp(a.firstname,b.firstname);});
> >
> > Last name:
> > myArray.sort(function(a,b){return cmp(a.lastname,b.lastname);});
> >
> > Id:
> > myArray.sort(function(a,b){return cmp(a.id,b.id);});
>
> Could you please explain this? Especially the inclusion of (a,b), and the
> {return ...} part... As I understood, the a and b shouldn't be put in the
> argument, only "myArray.sort(mySortFunction)"-style? I'm guessing that your
> method is the cool and fast power-user approach, so I REALLY want to
> understand it ;)
About anonymous functions:
You are probably familiar with the "normal" notation for functions
function functionname(arg1,arg2) {
...
}
This defines a named function, and you can later refer to it by its name.
I could have written
function compareFirstname(a,b) {
return cmp(a.firstname,b.firstname);
}
and then
myArray.sort(compareFirstname);
We can also define the same comparison function in this way:
var compareFirstname = function (a,b) {
return cmp(a.firstname,b.firstname);
}
That is, first we define a function with no name, and then we assign
it to a variable. This is equivalent to the above, the named function
definition can be seen as an abbreviation for explicitly naming an
anonymous function.
However, since we only need the function in one place, there is no need
to first give it a name and then use the name once. We could just put
the anonymous function definition directly where we need to use it. So, we
wrote
myArray.sort( function(a,b) { ... } );
About the function itself:
The myArray.sort function needs a comparison function to sort the array.
That comparison function must compare two elements of the array and return
-1 if the first is smaller, +1 if the second is smaller, and 0 if they
are equal.
The array contains objects (something with properties like .firstname
and .id). To sort the objects by the firstname property, we give the
myArray.sort an argument (a comparison function) that compares the
firstname properties of the objects.
So, the function needs to take two arguments, so it starts with
function (a,b) { // a and b are two elements of the array
This is an anonymous function, more on that later.
I use "a" and "b" for the parameters of the function. It is not important
what they are called, but "a" and "b" are somewhat traditional.
Now we need to return -1 if the firstname of a is smaller than the firstname
of b, and +1 if etc.
We have made a function, cmp, that can compare anything that
understand < and >. Firstname is a string, so it will do. So, we can
simply return the comparison of a.firstname and b.firstname:
return cmp(a.firstname,b.firstname);
}
> Also, if I'd like to stay with the arrays-in-an-array approach, could I just
> use a["lastname"] instead of a.lastname?
The two notations are, by definition of the language, completely equivalent.
> Are there any advantages to the object approach over the array
> approach?
The advantage of the a["x"] notatation over a.x is that the content of the
string need not be a single word. You can write
a["This is ridiculous, but it works"] = 42
and then later write
a["This is ridiculous, but it works"] + 1
to get 43.
There is no way to access that property with the .-notation.
In the end, for the code so far, it is merely a matter of style. I
have my ideas, but there are no fixed rules :)
There is another advantage of the []-notation. You don't have to use
a constant string, but can use a variable, where the .-notation requires
you to write the exact name of the property when you write the program.
So, you can write a function like
function getProperty(obj,prop) {
return obj[prop];
}
and then instead of writing a["x"] you can write getProperty(a,"x").
Not a big saving so far, but you can use it for some very pretty
solutions at times.
Look at this function (warning, advanced stuff, head may explode :):
function makeCmp(prop) {
return function (a,b) {
return cmp(a[prop],b[prop]);
};
}
This function takes one argument, the name of a property.
It returns a function that we *almost* recognize: one that compares
two objects by one of their properties. In this case, it is the property
that we have given as an argument to the outer function.
So:
makeCmp("firstname")
returns a function that compares two objects by their firstname property.
makeCmp("lastname")
returns a function that compares two objects by their lastname property.
So with this, you can write
myArray.sort(makeCmp("firstname"))
and
myArray.sort(makeCmp("lastname"))
(This is really functional programming. Experience shows that passing
functions around as arguments and (especially) having them returned as
results of other functions, can be very confuzing at first. It is also
a very powerfull tool at times, to the point where object oriented
people have begun emulating it. One example is the Visitor Pattern,
which is just basic functional programming weakly emulated. But that's
another discussion :)
> Sorry if I'm terribly much a newbie here!
It's a phase we have all been through :)
Don't despair if you don't understand all I say, I tend to take
off on a tangent given half a chance, as it probably shows.
Don't be afraid to ask.
Daniel
I can't believe you're taking so much time to go into such detail about
this! Thank you SO much! I asked about one thing, and now I know about
ten!!! =) You should be a teacher! I TOTALLY get this!
> function cmp(a,b) {
> return (a<b)?-1:(a>b)?1:0;
> }
cmp becomes -1 when a<b, 1 when a>b, otherwise 0, logic now =)
...and...
> function makeCmp(prop) {
> return function (a,b) {
> return cmp(a[prop],b[prop]);
> };
> }
makeCmp becomes a tailormade function derived from the cmp function, based
on the value of prop passed to makeCmp. I GET IT! Hehe, this is great!
And that .prop and ["prop"] are eachother's equivalent makes total sense,
since for JS an array would be just another object!
Man... Again, thank you so VERY much for your help and for being so kind!
You're the king!
Daniel =)
"Lasse Reichstein Nielsen" <l...@hotpop.com> wrote in message
news:7k80lm...@hotpop.com...
Dr John Stockton
in news:comp.lang.javascript, Daniel <sorry-no-email@i-get-virus-and-
spam.com> posted at Thu, 5 Jun 2003 12:44:41 :-
>
>This is my first visit here, and thus my first post ;)
Not so good; on the first visit to a newsgroup, you should find a
reference to its FAQ, and read that before posting.
>I'm trying to make a backend, and want to use Javascript to sort an array
>containing information about persons, each person has an associative array
>holding the data, like id, firstname, lastname, etc.
When I collected News, the thread had seven articles. There is one
point that I did not see mentioned.
Your example is small, rightly; the real job may be much bigger, say N
entries.
To sort N items by the most efficient method requires about o(N^x)
comparisons, where x is about 1.3. Each of these comparisons must,
ISTM, require a call of the comparison function. Therefore, for large
N, it can be worthwhile to do o(N) of preparatory work, if that can
speed up the comparisons.
The built-in comparison function of the sort() method really should be
at least as fast as, and probably faster than, anything that can be
coded in script as a sort function. So if an o(N) overhead allows use
of the default sort, it could be beneficial for large N.
Now I do not know just what the default sort does with an array whose
elements are themselves arrays, but it may be possible to arrange, by
setting in o(N) a sort-key, to get the desired effect from the default
function.
It might be that making each entry [key, name1, name2] and (in o(N))
doing for (J=0;J<L:J++) key[J] = Name1[J]) would lead to greater
speed.
--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MSIE 4 ©
<URL:http://jibbering.com/faq/> Jim Ley's FAQ for news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> JS maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/JS/&c., FAQ topics, links.
Lasse Reichstein Nielsen
> Your example is small, rightly; the real job may be much bigger, say N
> entries.
>
> To sort N items by the most efficient method requires about o(N^x)
> comparisons, where x is about 1.3.
I will bet that the internal sort algorithm in most Javascript
implementations is Quicksort, which has an expected execution time of
O(N*log_2(N)). That is slightly better than N^1.3 (isn't that the time
complexity of matrix multiplication?), but it point is, ofcourse,
still valid.
> Now I do not know just what the default sort does with an array whose
> elements are themselves arrays, but it may be possible to arrange, by
> setting in o(N) a sort-key, to get the desired effect from the default
> function.
It is a little more tricky than that. The internal comparison function
converts both arguments to strings[1]. To convert an arrays to a
string, convert each element to a string and 'join' them with commas.
That means that when comparing the two arrays
["foo","bar"]
and
["foo,ba","z"]
the first is actually the greater (since what is really compared is
"foo,bar" and "foo,ba,z" and "," < "r").
Using numbers is also dangerous, as "44"<"5".
I believe it can work, but it needs a lot of attention to details,
and it can easily become very fragile.
/L
[1] ECMAScript 3rd Ed., section 15.4.4.11, the SortCompare
operator, steps 16+17
Richard Cornford
<snip>
> var x = condition?expression1:expression2;
>
> It is shorter. I don't know if it is more efficient.
I did a speed test comparison of - if/else - against - ?: - once and
found no significant difference between the two. So the decision as to
which to use could not be based on efficiency.
<snip>
>>Also, if I'd like to stay with the arrays-in-an-array approach, could
I just
>>use a["lastname"] instead of a.lastname?
>
>The two notations are, by definition of the language, completely
equivalent.
<snip>
I also once speed tested dot notation property access against bracket
notation and found bracket notation consistently fractionally slower
(but it was only very fractionally slower). So they are not completely
equivalent, just so nearly equivalent that it makes no odds.
Richard.
Daniel
> Not so good; on the first visit to a newsgroup, you should find a
> reference to its FAQ, and read that before posting.
Sorry about that, I didn't know there was a FAQ - I found the group by
searching my news server for "javascript". Could you perhaps provide a link
to this FAQ?
> Now I do not know just what the default sort does with an array whose
> elements are themselves arrays, but it may be possible to arrange, by
> setting in o(N) a sort-key, to get the desired effect from the default
> function.
That was kind of what I hoped, but scouring the web and looking in my
Javascript bible (not the latest one, though) I didn't find any evidence of
such a method... Perhaps I'm not so good at picking out the right words (I'm
Danish), or maybe it's the vastness of search hits that causes me to not
find this info, but I don't think it's a native feature in Javascript.
> It might be that making each entry [key, name1, name2] and (in o(N))
> doing for (J=0;J<L:J++) key[J] = Name1[J]) would lead to greater
> speed.
You kinda lost me here, sorry :P... I still have a lot to learn ;)
Besides, the database this thing will most probably never have more than
500-1000 people in the list. Would this take very long to sort?
Thank you for your post! =)
Lasse Reichstein Nielsen
> I did a speed test comparison of - if/else - against - ?: - once and
> found no significant difference between the two. So the decision as to
> which to use could not be based on efficiency.
That was my expectation too. The low-level code that is executed will
be almost the same, only with the branching being done at a differ
point and some of the code duplicated in the two if brances.
> I also once speed tested dot notation property access against bracket
> notation and found bracket notation consistently fractionally slower
> (but it was only very fractionally slower). So they are not completely
> equivalent, just so nearly equivalent that it makes no odds.
In the language definition, they are defined to be (semantically)
equivalent, but the definition does (ofcourse) not talk about
efficiency (or all conforming implementations would perform the same
:)).
The slight overhead on the bracket notation probably comes from
dynamically converting a javascript string to an internal
representation.
If you write "foo.bar", then "bar" can be converted to a string in
an internal representation used by the interpreter at parse time.
If you write "foo['bar']", then "'bar'" is a javascript value, which
(in a lazily typed language) means that it has a tag associated with it
that tells us that it is a string (and probably something more too).
When using it for a property access, it must first be checked if it
is a string, and then the actual characters must be extracted into
an internal representation, which is then used to access the object's
[[GET]] method.
A smart compiler could optimize "foo['bar']" into "foo.bar", but if
you write "foo[x]", i.e. a dynamic property name, then there is also a
variable lookup which can not be optimized.
Dr John Stockton
news:comp.lang.javascript, Lasse Reichstein Nielsen <l...@hotpop.com>
posted at Fri, 6 Jun 2003 01:15:10 :-
>Dr John Stockton <sp...@merlyn.demon.co.uk> writes:
>> Now I do not know just what the default sort does with an array whose
>> elements are themselves arrays, but it may be possible to arrange, by
>> setting in o(N) a sort-key, to get the desired effect from the default
>> function.
>
>It is a little more tricky than that. The internal comparison function
>converts both arguments to strings[1]. To convert an arrays to a
>string, convert each element to a string and 'join' them with commas.
>Using numbers is also dangerous, as "44"<"5".
If the numbers are known to be less than, say, 1E14, then one can add
1E15 to each before sorting. Also convert to string before sorting, on
the O(N) vs O(NlogN) basis.
Thanks for mail & test.
--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Alex Russell
> Dr John Stockton <sp...@merlyn.demon.co.uk> writes:
>
>> Your example is small, rightly; the real job may be much bigger, say N
>> entries.
>>
>> To sort N items by the most efficient method requires about o(N^x)
>> comparisons, where x is about 1.3.
>
> I will bet that the internal sort algorithm in most Javascript
> implementations is Quicksort, which has an expected execution time of
> O(N*log_2(N)).
But a worst-case of O(N^2). It does, however, have the advantage of in-place
sorting to offset the worst-case speed.
I would have assumed that most browser would use a quicksort as well, save
that several months ago I wound up with a heavy sorting task that wasn't
exhibiting quicksort-like behavior on Mozilla. Seems spidermonkey doesn't
use a quicksort at all, instead it seems to use a heap sort, which is also
O(N*log_2(N)), but less memory efficient:
http://lxr.mozilla.org/seamonkey/source/js/src/jsarray.c#706
http://lxr.mozilla.org/seamonkey/source/js/src/jsarray.c#796
KJS, OTOH, seems to meet common expectations, as it uses qsort():
http://lxr.kde.org/source/kdelibs/kjs/array_object.cpp#L296
I don't suppose that either observation are particularly useful, but I found
the decision on the part of the Moz team interesting.
--
Alex Russell
al...@burstlib.org
al...@netWindows.org
Chris Riesbeck
"Daniel" <sorry-n...@i-get-virus-and-spam.com> wrote:
>Hi John! =)
>
>> Not so good; on the first visit to a newsgroup, you should find a
>> reference to its FAQ, and read that before posting.
>
>Sorry about that, I didn't know there was a FAQ - I found the group by
>searching my news server for "javascript". Could you perhaps provide a link
>to this FAQ?
Google: javascript faq
will show several. Usually people on this newsgroup
mean the one at
Dr John Stockton
in news:comp.lang.javascript, Daniel <sorry-no-email@i-get-virus-and-
>> Not so good; on the first visit to a newsgroup, you should find a
>> reference to its FAQ, and read that before posting.
>
>Sorry about that, I didn't know there was a FAQ - I found the group by
>searching my news server for "javascript". Could you perhaps provide a link
>to this FAQ?
I did.
--
© John Stockton, Surrey, UK. ???@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demon.co.uk/clpb-faq.txt> RAH Prins : c.l.p.b mFAQ;
<URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ.
Daniel
"Chris Riesbeck" <ries...@cs.northwestern.edu> wrote in message
news:riesbeck-ECD523...@news.it.northwestern.edu...