Javascript the good parts : sorting not stable?

Question

In the book "Javascript: The Good Parts", the author mentioned the concept "stable" in page 81. Link to Google book

However, I find that the example given by the book is irrelevant to whether the sort is stable or not. Wiki

Am I missing anything here?

So the example in the book is as follow:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];
The sort method is not stable, so:s.sort(by('first')).sort(by('last')); is not guaranteed to produce the correct sequence.

But this example actually doesn't prove if the sorting is stable or not. If sort by first then sort by last, the sort by first part will be overridden. The result is below:

[ { first: 'Joe', last: 'Besser' },
{ first: 'Joe', last: 'DeRita' },
{ first: 'Larry', last: 'Fine' },
{ first: 'Curly', last: 'Howard' },
{ first: 'Moe', last: 'Howard' },
{ first: 'Shemp', last: 'Howard' } ]

I know JS sort is not guaranteed stable. Here and here. But I don't think the book has treated the topic in the right way. My question is that I don't know if my understanding is correct or not. If I'm wrong I want to know why.

I don't know if my understanding is correct or not. If I'm wrong I want to know why. — theseadroid
– theseadroid, Commented May 9, 2015 at 2:24
"If sort by first then sort by last, the sort by first part will be overridden." - with a stable sort, the sort by last name will preserve the order created by the first sort for people with the same last name. — user2357112
– user2357112, Commented May 9, 2015 at 2:24
@Claies: The Howards are supposed to change order, due to the sort(by('first')). — user2357112
– user2357112, Commented May 9, 2015 at 2:26
@user245259—you should edit your question to actually ask that question then. ;-) To a large extent, this isn't really about javascript (or ECMAScript), it's really about sorting and what would be a better example of a non–stable sort. — RobG
– RobG, Commented May 9, 2015 at 2:27

user2357112 · Accepted Answer · 2015-05-09 02:35:08Z

Suppose you sort by first name, then re-sort by last name. You get something like this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    ?
    ?
    ?
]

The first three elements are guaranteed to be those three, but what are the rest? They all have the same last name 'Howard', so it's not clear what order they should be in.

With an unstable sort, those items could be in any order. You can get this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Shemp', last: 'Howard'}
    { first: 'Moe', last: 'Howard'},
    { first: 'Curly', last: 'Howard'},
]

where the last three elements are in reverse order of first name. However, with a stable sort, those elements would be guaranteed to come in the order they were placed in by the previous sort. The sort by first name put Curly ahead of Moe, who was ahead of Shemp, so you'd be guaranteed to get this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Curly', last: 'Howard'},
    { first: 'Moe', last: 'Howard'},
    { first: 'Shemp', last: 'Howard'}
]

Joshua Carmody · Accepted Answer · 2015-05-09 02:36:56Z

0

Looking at how "stable" was defined in the links you provided, and how the author of "Javascript: The Good Parts" used the word, I can see that the book did seem to be using a slightly different definition.

The author meant that Javascript sorts aren't "stable" in that you can't use cascading sort criteria without doing extra programming work. In some other languages, you can. For example, in C#, the following is valid LINQ:

// Sorts by two columns at once, no overwriting.
var sorted = s.OrderBy(p => p.FirstName).ThenBy(p => p.LastName);

It looks to me like that's what the author had in mind when he said "stable".

However, the Wiki and Mozilla docs you linked to in your question suggest that a "stable" sort should not change the relative order of items that have the same sort value. So using the following input data:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];

If I were to do an s.sort(by('last')); in Javascript, and it were stable, Moe Howard will always be listed before Shemp Howard, and Curly Howard would always be listed after Shemp. The sort would only take into account the last name, which is equal, and not change their relative order apart from that. If you were to sort the above list by last name and get the following results:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Curly', last: 'Howard'}
];

That would mean that the sort was not "stable" by Wikipedia's definition, since Shemp, Moe, and Curly changed positions relative to each other.

So to answer what I believe you were asking: The code in "Javascript: The Good Parts" does not demonstrate sort instability as defined by Wikipedia, because the author apparently was operating under a different definition of the word.

answered May 9, 2015 at 2:36

Joshua Carmody

13.8k16 gold badges68 silver badges85 bronze badges

2 Comments

user2357112 Over a year ago

These two definitions of "stable" are exactly equivalent. Any sort that makes one guarantee automatically fulfills the other.

user2357112 Over a year ago

Also, note that the author says "The sort method is not stable, so:s.sort(by('first')).sort(by('last')); is not guaranteed to produce the correct sequence." You might have been confused by how the OP's stated result is the result you'd get from a stable sort.

Collectives™ on Stack Overflow

Javascript the good parts : sorting not stable?

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related