Hi, sortBy is unstable meaning if I have a list of objects I''m sorting, and they are all being sorted by the same value, then the list will be returned in a random order every time. I think it is because it''s using the built in javascript array .sort function which isn''t stable either. Anyone know what to do about this? I don''t see how sortBy is useful beyond the most trivial applications unless it''s stable... Thanks in advance for your help. -Duane --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
The method''s name is sortBy - therefore it sorts BY something (as opposed to full sort involving all properties). I think having something like this in a core is too expensive - instead why not create your own method? btw, http://dev.rubyonrails.org/ticket/9936 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
Hi kangax, thanks for the response. Although I''m not asking for a sort that involves all properties, just a sort that doesn''t disturb the order of things that are ''equal'': Let''s say I''m sorting an array of li''s based on some property or innerHTML. If the innerHTML for each of the li''s is ''0'' then the the li''s will be returned by the sortBy function in a completely random order every time (and if there are different classes, events being observed, etc this will be apparent). On Oct 22, 4:29 pm, kangax <kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> The method''s name is sortBy - therefore it sorts BY something (as > opposed to full sort involving all properties). I think having > something like this in a core is too expensive - instead why not > create your own method? > > btw,http://dev.rubyonrails.org/ticket/9936--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
I looked at your reply in the include link in your above note. We aren''t asking to support n-level sorting, just stable sorting. In other words, don''t change the order of things that are ''equal''. As it is, when you sort an enumerable of all ''equal'' values it returns the enumerable in a random order. On Oct 22, 4:29 pm, kangax <kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> The method''s name is sortBy - therefore it sorts BY something (as > opposed to full sort involving all properties). I think having > something like this in a core is too expensive - instead why not > create your own method? > > btw,http://dev.rubyonrails.org/ticket/9936--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
I think what kangax is getting at is that sortBy uses the underlying
array.sort method (which is native javascript).
To change the behaviour would require prototype to modify this, which
according to POLS would be bad - people may not expect the underlying sort
to be different.
The best solution for you would be to implement your own sort algorithm on
the array using a prototype.
Array.prototype.sort = function() {
//sort the array.
//''this'' will refer to the array itself, not the function.
}
This will override the default sort behaviour.
Gareth
On 10/23/07, duane.barlow
<duane.barlow-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
wrote:>
>
> I looked at your reply in the include link in your above note. We
> aren''t asking to support n-level sorting, just stable sorting. In
> other words, don''t change the order of things that are
''equal''. As it
> is, when you sort an enumerable of all ''equal'' values it
returns the
> enumerable in a random order.
>
> On Oct 22, 4:29 pm, kangax
<kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > The method''s name is sortBy - therefore it sorts BY something
(as
> > opposed to full sort involving all properties). I think having
> > something like this in a core is too expensive - instead why not
> > create your own method?
> >
> > btw,http://dev.rubyonrails.org/ticket/9936
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Ruby on Rails: Spinoffs" group.
To post to this group, send email to
rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
To unsubscribe from this group, send email to
rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
For more options, visit this group at
http://groups.google.com/group/rubyonrails-spinoffs?hl=en
-~----------~----~----~----~------~----~------~--~---
Oops, the sort prototype function should take an iterator function
function (left,right) {
}
so Array.prototype.sort = function(obj) {
}
or you''ll break prototype sortBy.
On 10/23/07, Gareth Evans <agrath-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
wrote:>
> I think what kangax is getting at is that sortBy uses the underlying
> array.sort method (which is native javascript).
> To change the behaviour would require prototype to modify this, which
> according to POLS would be bad - people may not expect the underlying sort
> to be different.
> The best solution for you would be to implement your own sort algorithm on
> the array using a prototype.
>
> Array.prototype.sort = function() {
> //sort the array.
> //''this'' will refer to the array itself, not the
function.
> }
> This will override the default sort behaviour.
>
> Gareth
>
> On 10/23/07, duane.barlow
<duane.barlow-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote:
> >
> >
> > I looked at your reply in the include link in your above note. We
> > aren''t asking to support n-level sorting, just stable
sorting. In
> > other words, don''t change the order of things that are
''equal''. As it
> > is, when you sort an enumerable of all ''equal''
values it returns the
> > enumerable in a random order.
> >
> > On Oct 22, 4:29 pm, kangax
<kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > > The method''s name is sortBy - therefore it sorts BY
something (as
> > > opposed to full sort involving all properties). I think having
> > > something like this in a core is too expensive - instead why not
> > > create your own method?
> > >
> > > btw,http://dev.rubyonrails.org/ticket/9936
> >
> >
> > > >
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Ruby on Rails: Spinoffs" group.
To post to this group, send email to
rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
To unsubscribe from this group, send email to
rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
For more options, visit this group at
http://groups.google.com/group/rubyonrails-spinoffs?hl=en
-~----------~----~----~----~------~----~------~--~---
Hi Gareth, thanks for the suggestion. I''ll implement an in-place merge-sort to override Array.sort and post it back here in case anyone else wants stable sorting. Is this the place where one should do that? Is there a better place to post changes people might want? -Duane On Oct 22, 5:25 pm, "Gareth Evans" <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> Oops, the sort prototype function should take an iterator function > > function (left,right) { > > } > > so Array.prototype.sort = function(obj) { > > } > > or you''ll break prototype sortBy. > > On 10/23/07, Gareth Evans <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > I think what kangax is getting at is that sortBy uses the underlying > > array.sort method (which is native javascript). > > To change the behaviour would require prototype to modify this, which > > according to POLS would be bad - people may not expect the underlying sort > > to be different. > > The best solution for you would be to implement your own sort algorithm on > > the array using a prototype. > > > Array.prototype.sort = function() { > > //sort the array. > > //''this'' will refer to the array itself, not the function. > > } > > This will override the default sort behaviour. > > > Gareth > > > On 10/23/07, duane.barlow <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote: > > > > I looked at your reply in the include link in your above note. We > > > aren''t asking to support n-level sorting, just stable sorting. In > > > other words, don''t change the order of things that are ''equal''. As it > > > is, when you sort an enumerable of all ''equal'' values it returns the > > > enumerable in a random order. > > > > On Oct 22, 4:29 pm, kangax <kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > The method''s name is sortBy - therefore it sorts BY something (as > > > > opposed to full sort involving all properties). I think having > > > > something like this in a core is too expensive - instead why not > > > > create your own method? > > > > > btw,http://dev.rubyonrails.org/ticket/9936--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
yup post it here, just make sure you test default sort behaviour so that it''s a drop in replacement. i.e.: don''t break the native sorting, so support an iterator function as well as no iterator. Gareth On 10/23/07, duane.barlow <duane.barlow-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> > > Hi Gareth, thanks for the suggestion. > I''ll implement an in-place merge-sort to override Array.sort and post > it back here in case anyone else wants stable sorting. > Is this the place where one should do that? Is there a better place > to post changes people might want? > -Duane > > On Oct 22, 5:25 pm, "Gareth Evans" <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > Oops, the sort prototype function should take an iterator function > > > > function (left,right) { > > > > } > > > > so Array.prototype.sort = function(obj) { > > > > } > > > > or you''ll break prototype sortBy. > > > > On 10/23/07, Gareth Evans <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > > > > > I think what kangax is getting at is that sortBy uses the underlying > > > array.sort method (which is native javascript). > > > To change the behaviour would require prototype to modify this, which > > > according to POLS would be bad - people may not expect the underlying > sort > > > to be different. > > > The best solution for you would be to implement your own sort > algorithm on > > > the array using a prototype. > > > > > Array.prototype.sort = function() { > > > //sort the array. > > > //''this'' will refer to the array itself, not the function. > > > } > > > This will override the default sort behaviour. > > > > > Gareth > > > > > On 10/23/07, duane.barlow <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote: > > > > > > I looked at your reply in the include link in your above note. We > > > > aren''t asking to support n-level sorting, just stable sorting. In > > > > other words, don''t change the order of things that are ''equal''. As > it > > > > is, when you sort an enumerable of all ''equal'' values it returns the > > > > enumerable in a random order. > > > > > > On Oct 22, 4:29 pm, kangax <kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > The method''s name is sortBy - therefore it sorts BY something (as > > > > > opposed to full sort involving all properties). I think having > > > > > something like this in a core is too expensive - instead why not > > > > > create your own method? > > > > > > > btw,http://dev.rubyonrails.org/ticket/9936 > > > > >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
OK, so below is the mergesort (not in-place) replacement.
There are probably ways of improving this (my efficiency with basic
array manipulation is somewhat rusty), let me know what you think.
*One important question/bug*: my ''default'' compare function
doesn''t
work the same as the default compare function for the regular sort.
The regular Array.sort() function will treat an array of numbers (eg
[1,3,2,11]) as strings (and return [1,11,2,3]) but my compare function
treats them as integers (and returns [1,2,3,11]).
Could someone take a look at my default compareFunction (line 2) and
tell me what is causing this?
Thanks for your help, the code is below:
Array.prototype.sort = function (compareFunction) {
if (!compareFunction) { compareFunction = function (left, right)
{ var a = left.criteria, b = right.criteria;return a < b ? -1 : a >
b ? 1 : 0; }}
var mergeSort = function (list) {
var left, right, result;
if (list.length <= 1)
return list;
else {
var middle = parseInt(list.length / 2);
left = list.splice(0, middle);
right = list;
left = mergeSort(left);
right = mergeSort(right);
result = merge(left, right);
return result;
}
}
var merge = function(left, right) {
var result = [];
while (left.length > 0 && right.length > 0) {
if (compareFunction({criteria:left[0]}, {criteria:right[0]}) <= 0)
{
result.push(left[0]);
left = left.splice(1, left.length);
} else {
result.push(right[0]);
right = right.splice(1, right.length);
}
}
while (left.length > 0) {
result.push(left[0]);
left = left.splice(1, left.length);
} while (right.length > 0) {
result.push(right[0]);
right = right.splice(1, right.length);
}
return result;
}
var tempArray = this;
tempArray = mergeSort(tempArray);
for (var i = 0; i < tempArray.length; i++) {
this[i] = tempArray[i];
}
return this;
}
On Oct 22, 5:43 pm, "Gareth Evans"
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
wrote:> yup post it here, just make sure you test default sort behaviour so that
> it''s a drop in replacement.
> i.e.: don''t break the native sorting, so support an iterator
function as
> well as no iterator.
>
> Gareth
>
> On 10/23/07, duane.barlow
<duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
>
>
> > Hi Gareth, thanks for the suggestion.
> > I''ll implement an in-place merge-sort to override Array.sort
and post
> > it back here in case anyone else wants stable sorting.
> > Is this the place where one should do that? Is there a better place
> > to post changes people might want?
> > -Duane
>
> > On Oct 22, 5:25 pm, "Gareth Evans"
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > > Oops, the sort prototype function should take an iterator
function
>
> > > function (left,right) {
>
> > > }
>
> > > so Array.prototype.sort = function(obj) {
>
> > > }
>
> > > or you''ll break prototype sortBy.
>
> > > On 10/23/07, Gareth Evans
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
> > > > I think what kangax is getting at is that sortBy uses the
underlying
> > > > array.sort method (which is native javascript).
> > > > To change the behaviour would require prototype to modify
this, which
> > > > according to POLS would be bad - people may not expect the
underlying
> > sort
> > > > to be different.
> > > > The best solution for you would be to implement your own
sort
> > algorithm on
> > > > the array using a prototype.
>
> > > > Array.prototype.sort = function() {
> > > > //sort the array.
> > > > //''this'' will refer to the array itself,
not the function.
> > > > }
> > > > This will override the default sort behaviour.
>
> > > > Gareth
>
> > > > On 10/23/07, duane.barlow
<duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote:
>
> > > > > I looked at your reply in the include link in your
above note. We
> > > > > aren''t asking to support n-level sorting, just
stable sorting. In
> > > > > other words, don''t change the order of things
that are ''equal''. As
> > it
> > > > > is, when you sort an enumerable of all
''equal'' values it returns the
> > > > > enumerable in a random order.
>
> > > > > On Oct 22, 4:29 pm, kangax
<kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > > > > > The method''s name is sortBy - therefore
it sorts BY something (as
> > > > > > opposed to full sort involving all properties). I
think having
> > > > > > something like this in a core is too expensive -
instead why not
> > > > > > create your own method?
>
> > > > > > btw,http://dev.rubyonrails.org/ticket/9936
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Ruby on Rails: Spinoffs" group.
To post to this group, send email to
rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
To unsubscribe from this group, send email to
rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
For more options, visit this group at
http://groups.google.com/group/rubyonrails-spinoffs?hl=en
-~----------~----~----~----~------~----~------~--~---
Please replace line 2 with below (note, this doesn''t fix the problem I
mentioned above).
if (!compareFunction) { compareFunction = function (a, b) { return a <
b ? -1 : a > b ? 1 : 0; }}
On Oct 23, 10:25 am, "duane.barlow"
<duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
wrote:> OK, so below is the mergesort (not in-place) replacement.
> There are probably ways of improving this (my efficiency with basic
> array manipulation is somewhat rusty), let me know what you think.
> *One important question/bug*: my ''default'' compare
function doesn''t
> work the same as the default compare function for the regular sort.
> The regular Array.sort() function will treat an array of numbers (eg
> [1,3,2,11]) as strings (and return [1,11,2,3]) but my compare function
> treats them as integers (and returns [1,2,3,11]).
> Could someone take a look at my default compareFunction (line 2) and
> tell me what is causing this?
>
> Thanks for your help, the code is below:
> Array.prototype.sort = function (compareFunction) {
> if (!compareFunction) { compareFunction = function (left, right)
> { var a = left.criteria, b = right.criteria;return a < b ? -1 : a >
> b ? 1 : 0; }}
> var mergeSort = function (list) {
> var left, right, result;
> if (list.length <= 1)
> return list;
> else {
> var middle = parseInt(list.length / 2);
> left = list.splice(0, middle);
> right = list;
> left = mergeSort(left);
> right = mergeSort(right);
> result = merge(left, right);
> return result;
> }
> }
> var merge = function(left, right) {
> var result = [];
> while (left.length > 0 && right.length > 0) {
> if (compareFunction({criteria:left[0]},
{criteria:right[0]}) <= 0)
> {
> result.push(left[0]);
> left = left.splice(1, left.length);
> } else {
> result.push(right[0]);
> right = right.splice(1, right.length);
> }
> }
> while (left.length > 0) {
> result.push(left[0]);
> left = left.splice(1, left.length);
> } while (right.length > 0) {
> result.push(right[0]);
> right = right.splice(1, right.length);
> }
> return result;
> }
> var tempArray = this;
> tempArray = mergeSort(tempArray);
> for (var i = 0; i < tempArray.length; i++) {
> this[i] = tempArray[i];
> }
> return this;
>
> }
>
> On Oct 22, 5:43 pm, "Gareth Evans"
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
> > yup post it here, just make sure you test default sort behaviour so
that
> > it''s a drop in replacement.
> > i.e.: don''t break the native sorting, so support an iterator
function as
> > well as no iterator.
>
> > Gareth
>
> > On 10/23/07, duane.barlow
<duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
> > > Hi Gareth, thanks for the suggestion.
> > > I''ll implement an in-place merge-sort to override
Array.sort and post
> > > it back here in case anyone else wants stable sorting.
> > > Is this the place where one should do that? Is there a better
place
> > > to post changes people might want?
> > > -Duane
>
> > > On Oct 22, 5:25 pm, "Gareth Evans"
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > > > Oops, the sort prototype function should take an iterator
function
>
> > > > function (left,right) {
>
> > > > }
>
> > > > so Array.prototype.sort = function(obj) {
>
> > > > }
>
> > > > or you''ll break prototype sortBy.
>
> > > > On 10/23/07, Gareth Evans
<agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
> > > > > I think what kangax is getting at is that sortBy uses
the underlying
> > > > > array.sort method (which is native javascript).
> > > > > To change the behaviour would require prototype to
modify this, which
> > > > > according to POLS would be bad - people may not expect
the underlying
> > > sort
> > > > > to be different.
> > > > > The best solution for you would be to implement your
own sort
> > > algorithm on
> > > > > the array using a prototype.
>
> > > > > Array.prototype.sort = function() {
> > > > > //sort the array.
> > > > > //''this'' will refer to the array
itself, not the function.
> > > > > }
> > > > > This will override the default sort behaviour.
>
> > > > > Gareth
>
> > > > > On 10/23/07, duane.barlow
<duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote:
>
> > > > > > I looked at your reply in the include link in your
above note. We
> > > > > > aren''t asking to support n-level sorting,
just stable sorting. In
> > > > > > other words, don''t change the order of
things that are ''equal''. As
> > > it
> > > > > > is, when you sort an enumerable of all
''equal'' values it returns the
> > > > > > enumerable in a random order.
>
> > > > > > On Oct 22, 4:29 pm, kangax
<kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> > > > > > > The method''s name is sortBy -
therefore it sorts BY something (as
> > > > > > > opposed to full sort involving all
properties). I think having
> > > > > > > something like this in a core is too
expensive - instead why not
> > > > > > > create your own method?
>
> > > > > > > btw,http://dev.rubyonrails.org/ticket/9936
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Ruby on Rails: Spinoffs" group.
To post to this group, send email to
rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
To unsubscribe from this group, send email to
rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org
For more options, visit this group at
http://groups.google.com/group/rubyonrails-spinoffs?hl=en
-~----------~----~----~----~------~----~------~--~---
Please excuse my ignorance, but why would having sortBy use a different sorting algorithm than the core JS sort be bad? You don''t have to overwrite/replace sort. If it''s about people''s expectations, the documentation says that ''Elements of equivalent criterion value are left in existing order''. So, I assumed that this function was what I was looking for. I agree with Duane that sortBy isn''t extremely useful unless it provides this functionality. Plain sort would suffice. And, what is POLS? Thanks. On Oct 23, 9:57 am, "duane.barlow" <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> Please replace line 2 with below (note, this doesn''t fix the problem I > mentioned above). > if (!compareFunction) { compareFunction = function (a, b) { return a < > b ? -1 : a > b ? 1 : 0; }} > > On Oct 23, 10:25 am, "duane.barlow" <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > OK, so below is the mergesort (not in-place) replacement. > > There are probably ways of improving this (my efficiency with basic > > array manipulation is somewhat rusty), let me know what you think. > > *One important question/bug*: my ''default'' compare function doesn''t > > work the same as the default compare function for the regular sort. > > The regular Array.sort() function will treat an array of numbers (eg > > [1,3,2,11]) as strings (and return [1,11,2,3]) but my compare function > > treats them as integers (and returns [1,2,3,11]). > > Could someone take a look at my default compareFunction (line 2) and > > tell me what is causing this? > > > Thanks for your help, the code is below: > > Array.prototype.sort = function (compareFunction) { > > if (!compareFunction) { compareFunction = function (left, right) > > { var a = left.criteria, b = right.criteria;return a < b ? -1 : a > > > b ? 1 : 0; }} > > var mergeSort = function (list) { > > var left, right, result; > > if (list.length <= 1) > > return list; > > else { > > var middle = parseInt(list.length / 2); > > left = list.splice(0, middle); > > right = list; > > left = mergeSort(left); > > right = mergeSort(right); > > result = merge(left, right); > > return result; > > } > > } > > var merge = function(left, right) { > > var result = []; > > while (left.length > 0 && right.length > 0) { > > if (compareFunction({criteria:left[0]}, {criteria:right[0]}) <= 0) > > { > > result.push(left[0]); > > left = left.splice(1, left.length); > > } else { > > result.push(right[0]); > > right = right.splice(1, right.length); > > } > > } > > while (left.length > 0) { > > result.push(left[0]); > > left = left.splice(1, left.length); > > } while (right.length > 0) { > > result.push(right[0]); > > right = right.splice(1, right.length); > > } > > return result; > > } > > var tempArray = this; > > tempArray = mergeSort(tempArray); > > for (var i = 0; i < tempArray.length; i++) { > > this[i] = tempArray[i]; > > } > > return this; > > > } > > > On Oct 22, 5:43 pm, "Gareth Evans" <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > yup post it here, just make sure you test default sort behaviour so that > > > it''s a drop in replacement. > > > i.e.: don''t break the native sorting, so support an iterator function as > > > well as no iterator. > > > > Gareth > > > > On 10/23/07, duane.barlow <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > Hi Gareth, thanks for the suggestion. > > > > I''ll implement an in-place merge-sort to override Array.sort and post > > > > it back here in case anyone else wants stable sorting. > > > > Is this the place where one should do that? Is there a better place > > > > to post changes people might want? > > > > -Duane > > > > > On Oct 22, 5:25 pm, "Gareth Evans" <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > Oops, the sort prototype function should take an iterator function > > > > > > function (left,right) { > > > > > > } > > > > > > so Array.prototype.sort = function(obj) { > > > > > > } > > > > > > or you''ll break prototype sortBy. > > > > > > On 10/23/07, Gareth Evans <agr...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > > > I think what kangax is getting at is that sortBy uses the underlying > > > > > > array.sort method (which is native javascript). > > > > > > To change the behaviour would require prototype to modify this, which > > > > > > according to POLS would be bad - people may not expect the underlying > > > > sort > > > > > > to be different. > > > > > > The best solution for you would be to implement your own sort > > > > algorithm on > > > > > > the array using a prototype. > > > > > > > Array.prototype.sort = function() { > > > > > > //sort the array. > > > > > > //''this'' will refer to the array itself, not the function. > > > > > > } > > > > > > This will override the default sort behaviour. > > > > > > > Gareth > > > > > > > On 10/23/07, duane.barlow <duane.bar...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org > wrote: > > > > > > > > I looked at your reply in the include link in your above note. We > > > > > > > aren''t asking to support n-level sorting, just stable sorting. In > > > > > > > other words, don''t change the order of things that are ''equal''. As > > > > it > > > > > > > is, when you sort an enumerable of all ''equal'' values it returns the > > > > > > > enumerable in a random order. > > > > > > > > On Oct 22, 4:29 pm, kangax <kan...-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote: > > > > > > > > The method''s name is sortBy - therefore it sorts BY something (as > > > > > > > > opposed to full sort involving all properties). I think having > > > > > > > > something like this in a core is too expensive - instead why not > > > > > > > > create your own method? > > > > > > > > > btw,http://dev.rubyonrails.org/ticket/9936--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
On Oct 23, 2007, at 12:39 PM, Jupiter ITS wrote:> And, what is POLS?Principle of Least Surprise http://en.wikipedia.org/wiki/Principle_of_least_surprise GIYF =) TAG --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---
Tom, that''s a lot of abbreviations in one post : ) @Jupiter ITS @duane.barlow I see exactly what you mean now. This definitely looks like a bug to me. sortBy internally uses native sort (just wraps it conveniently) but somehow (due to reasons beyond my understanding) messes up the existing order. MDC states that: "If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this." The funny thing is that native sort gets it right and leaves the order intact, but prototype (essentially doing the same thing!!!) does not. The ticket is opened, so you''re welcome to poke around and tell us what the problem might be. Best, kangax --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Spinoffs" group. To post to this group, send email to rubyonrails-spinoffs-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-spinoffs-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-spinoffs?hl=en -~----------~----~----~----~------~----~------~--~---