Skip to content

Instantly share code, notes, and snippets.

@masak
Last active September 2, 2019 07:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save masak/4225a65ff0839f35b2f0357a77c64f20 to your computer and use it in GitHub Desktop.
Save masak/4225a65ff0839f35b2f0357a77c64f20 to your computer and use it in GitHub Desktop.
Edument blog post: Surviving sorting in JavaScript

A built-in .sort() method, how hard can it be to get it right? Taking JavaScript as our yardstick, apparently really quite hard. Read about two major pitfalls that anyone who wants to sort arrays in JavaScript should be aware of.

En inbyggd .sort()-metod, hur svårt kan det vara att få den rätt? Tar vi JavaScript som vår måttstock så är det tydligentydligen riktigt svårt. Läs om två större fallgropar som alla som tänker sortera strayer i JavaScript bör känna till.

JavaScript has a .sort method, but this method comes with a number of sharp corners. This blog post explains how to learn to live with sorting in JavaScript.

The ancient art of arranging elements

Here's the .sort method:

> ["banana", "coconut", "apple"].sort()
["apple", "banana", "coconut"]

Easy-peasy! As you can see above, .sort() returns the sorted result.

But, as a salesman on late-night TV might put it, that's not all! Instead of giving you a new array with the elements sorted, JavaScript's sort method is in-place — it uses the array you passed in to re-arrange the items.

> let fruits = ["banana", "coconut", "apple"]
> fruits.sort()
> // the array `fruits` is now sorted: `["apple", "banana", "coconut"]`

You read that right. JavaScript's .sort() both modifies the array, and returns it.

Because of this, it's slightly bad style to assign the result of the sort back to the original array:

> fruits = fruits.sort();     // don't do this!

It's not wrong per se, it's just redundant, akin to cooking your dinner an extra time when it's already cooked. My advice is to never assign in connection with .sort(). (Chaining sorts is fine, since we're dealing with the same array reference all the time. But it's wrong because of the lack of stability; see later in this post.)

It's also important in contexts that demand immutability (such as Redux) to remember that .sort() clobbers the original array; if this is not acceptable, you can clone the array before sorting:

> let sortedFruits = [...fruits].sort();

Math is hard, let's go shopping

Since we had such amazing success with fruits, we immediately turn to numbers:

> [1, 2, 17, 24, 123, 1024].sort()
[1, 1024, 123, 17, 2, 24]

Oh no! JavaScript's answer runs up aginst our deeply-held beliefs about the order numbers appear on the real number line!

What's going on here? The reason the fruits came out right but the numbers didn't is that JavaScript's sort is lexicographical by default. It compares everything as strings — and indeed, "1024" would appear somewhere between "1" and "123" in a (truly huge) dictionary of numbers.

(Cue a legion of upset readers emailing me about the impossibility of putting all the real numbers, in order, into a dictionary. Dear hypothetical irate readers, calm down. We're only talking about putting all the IEEE 754 double-precision floating-point numbers into a dictionary. This is still a very stupid thing to do, but clearly doable.)

Before we look at how to fix numerical sorting, we might ask why the default is lexicographic order. I think there are two related reasons:

  • JavaScript, being loosely typed, doesn't see "array of strings" or "array of numbers"; it just sees "array". In a sense, it has to decide on a default sorting order without knowing anything about the types of the array's elements.

  • If we were to pick a sorting order that works for everything, including heterogenous arrays containing mixed types, then lexicographic order is it. This is based on the deep theory of "everything can be turned into a string, however badly".

Fixing numerical sorting

As the MDN page for Array.prototype.sort points out, the .sort() method accepts an optional compareFunction parameter. This is how we get into the game of specifying the order, for example numerical order.

function compareNumerically(a, b) {
    if (Number(a) < Number(b)) {
        return -1;
    } else if (Number(a) > Number(b)) {
        return +1;
    } else {
        return 0;
    }
}

A compare function like the one above promises to adhere to a protocol, namely to return -1, 0, or +1 depending on the relative ordering between its two parameters. (It's allowed to return any positive or negative value, but you will rarely need this.) -1 means "a is less than b", 0 means "a and b are equal", +1 means "a is greater than b".

But not just that. The .sort() method expects the compare function to be consistent, and return the same output for the same inputs. It also expects the compare function to specify a total order, that is, all the elements can be placed in some order on a line such as the number line. (It is ok for values to compare as equal even if they are not identical. More about that below.)

If you ask me, the -1, 0, +1 values are slightly magical and unexplained. They belong to a bygone era where such protocols were considered cute and knowing about them was part of belonging to the in-group of battle-scarred programmers. We can do better by naming the constants for what they represent:

const LESS = -1, EQUAL = 0, GREATER = +1;

function compareNumerically(a, b) {
    if (Number(a) < Number(b)) {
        return LESS;
    } else if (Number(a) > Number(b)) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

Now the numeric sort works:

> [1, 2, 17, 24, 123, 1024].sort(compareNumerically)
[1, 2, 17, 24, 123, 1024]

A quick aside: because we're allowed to return any positive or negative number from a compare function, this shorter version would also do the trick:

function compareNumerically(a, b) { return a - b }

But, as we will see below, we will get more benefits in this blog post by sticking to the longer, spelled-out implementation.

Comparing by property

Let's say, hypothetically, that I have so many computer games that I need to keep track of them in a little database and show them in a table on a web page. A game is represented by this class:

class Game {
    constructor(title, publisher, year) {
        this.title = title;
        this.publisher = publisher;
        this.year = year;
    }
}

Keep in mind, this is hundreds of games we're talking about. Hypothetically. If we have an array of games, how do we sort them sensibly?

Emboldened by our success with the numbers, we can define a sorting function for each of the properties of a game:

function compareByTitle(a, b) {
    if (a.title < b.title) {
        return LESS;
    } else if (a.title > b.title) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

function compareByPublisher(a, b) {
    if (a.publisher < b.publisher) {
        return LESS;
    } else if (a.publisher > b.publisher) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

function compareByYear(a, b) {
    if (a.year < b.year) {
        return LESS;
    } else if (a.year > b.year) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

Phew! That's a lot of code. Not only that, it's a lot of repetitive code. That's, like, the worst kind.

If we squint at the three functions, we see that they're all doing the same thing, but with different properties. That is, we can factor out the "compare by property" part from the part that specifies the specific property. Here, let's make a function that returns a custom compare function:

function compareByProperty(p) {
    return (a, b) => {
        if (a[p] < b[p]) {
            return LESS;
        } else if (a[p] > b[p]) {
            return GREATER;
        } else {
            return EQUAL;
        }
    };
}

Now the three compare functions can be defined super-simply, the sweet reward for keeping things DRY:

let compareByTitle = compareByProperty("title");
let compareByPublisher = compareByProperty("publisher");
let compareByYear = compareByProperty("year");

That's nice, but we can go one step further. We can factor out the "compare by" part from the "property" part! Behold:

function compareBy(fn) {
    return (a, b) => {
        if (fn(a) < fn(b)) {
            return LESS;
        } else if (fn(a) > fn(b)) {
            return GREATER;
        } else {
            return EQUAL;
        }
    };
}

function property(p) {
    return (e) => e[p];
}

Our property compare functions now look like this:

let compareByTitle = compareBy(property("title"));
let compareByPublisher = compareBy(property("publisher"));
let compareByYear = compareBy(property("year"));

What did we gain from this last factoring? The compareBy function is more general, and can swallow up the compareNumerically function we laboriously defined above:

let compareNumerically = compareBy(Number);

It's nice when things get easier! And it reads nicely, too. "Compare by Number".

Doing the same thing with other wrapper types would also work: compareBy(Boolean), and compareBy(String). Again, the latter is the default, so we don't need to specify it unless we want to be explicit.

Taking a step back, this is nice simply because it aligns better with our intuition about sorting. The "compare function" convention with -1, 0, and +1 is flexible, but it's not intuitive. Often the thought we want to express is "compare based on something that we can compute from each element". This is what compareBy does. Java 8 adds a static method Comparator.comparing which also does exactly this.

Very stable genius

I need to show my games in some nice predictable order on the page. Let's say I want to order them primarily by publisher, but for every publisher I want them sorted by title. So the problem is "Sort by publisher, and then (if games have the same publisher) by title".

Can we do this in JavaScript? The answer is of course yes, but JavaScript will be damned if it makes life easy for us.

One moderately clever thing we can attempt is to sort twice:

games.sort(compareByTitle)
     .sort(compareByPublisher);  // note: DON'T DO THIS -- see explanation below

Note the backwards thinking here: since we want the games to be sorted primarily by publisher, we do that sort last. This reasoning is weird but correct.

In order for this to work, the second sort will need to respect and preserve the sorted-by-title order from the first sort, whenever it compares two games by the same publisher. That is, if compareByPublisher says that the result is EQUAL then .sort() should say "fine, I'll just keep the order as it already is".

A sorting algorithm that does this is called stable. It's not a tautological property — a sorting algorithm can also be unstable, in which case it makes no guarantees about the final order of EQUAL elements (and very likely jumbles them).

So... the question becomes is JavaScript's sort guaranteed to be stable?

And the answer, as you already suspected with that sinking feeling in your stomach, is no. It would be terribly useful for us to be able to assume a stable sort. But with JavaScript's built-in .sort(), you can't assume that. JavaScript is many things, but it's not your best buddy.

We speak often about JavaScript, but in reality there are multiple implementations of JavaScript out there. Currently, there are these major implementations:

  • v8 (Chrome, Node.js) — unstable sort
  • JavaScriptCore (Safari) — stable sort
  • SpiderMonkey (Firefox) — stable sort
  • ChakraCore (Edge) — stable sort

On v8, sorting is unstable. In all the other major browsers, sorting is stable. (In older versions of Firefox and Opera, sorting used to be unstable.) If we want our code to work the same across all browsers, past and present, we cannot assume stability.

(In fact, the situation with v8 is even more detailed than that. If your array happens to have 10 elements or fewer, that sort will be stable, because v8 falls back on insertion sort for performance reasons, and insertion sort is stable! So you will get a stable sort sometimes, for the kind of short lists you are likely to use as test cases.)

Ok, so forget about the implementations. What does the ECMAScript specification have to say about the stability of sorting? Maybe we can force the specification down the implementors' throats?

The elements of this array are sorted. The sort is not necessarily stable [...]

Apparently not. Thanks for nothing, ECMAScript specification!

By the way, JavaScript is in fairly good company here. Some languages (Java, Python) have a built-in library sort function that guarantees stability, whereas other languages (Ruby, C#) don't. It seems to be connected to the fact that traditionally, there has been no good way to make QuickSort stable and maximally performant at the same time. Stability sacrificed for speed.

Fixing stable sort

Thinking about how to make sorting stable, what we need is a "chained compare function" which does what stable sort should have done for us automatically: it compares by publisher first, and if those come out equal, it falls back to comparing by title:

function compareByPublisherThenTitle(a, b) {
    if (a.publisher < b.publisher) {
        return LESS;
    } else if (a.publisher > b.publisher) {
        return GREATER;
    } else {
        if (a.title < b.title) {
            return LESS;
        } else if (a.title > b.title) {
            return GREATER;
        } else {
            return EQUAL;
        }
    }
}

Visually, this code looks like one compare function shoved into another compare function. And yes, this works:

> games.sort(compareByPublisherThenTitle);

But clearly we can do better, in terms of factoring out common solutions. How about if we have a "chained compare", that can coordinate between two compare functions, falling back to the second if the first returns EQUAL?

function chained(fn1, fn2) {
    return (a, b) => {
        let v = fn1(a, b);
        return v === EQUAL
            ? fn2(a, b)
            : v;
    };
}

Now we can use this chaining mechanism instead of manually writing a huge combined compare function:

let compareByPublisherThenTitle = chained(compareByPublisher, compareByTitle);

Or, if we want:

let compareByPublisherThenTitle = chained(compareBy(property("publisher")), compareBy(property("title")));

Stable sort on an existing array

The above is fine for the cases where we don't care about the existing order of the elements. But we can also imagine scenarios where we do.

Consider for example that the games are listed in a table on a page, and the table has clickable headings "title", "publisher", and "year". Clicking on a heading allows you to sort the games based on that property.

Of course we want this sort to be stable too; that is, any order that already exists among the table rows should be preserved when possible. In this case JavaScript's unstable sort is working maximally against us, and we have to be creative.

In order to preserve the existing order, we would like to arrive at a situation where we can write compareBy(property("index")), where the index property contains the array index of the element. Unfortunately, there's no such index property in general... so what the below code does is to temporarily add such a property before sorting, and then peel it away afterwards.

let indexedGames = games.map((value, index) => ({ value, index }));
let compareByPropertyStable = (p) => chained(compareBy((e) => e.value[p]), compareBy(property("index")));
indexedGames.sort(compareByPropertyStable("year"));     // for example
games = indexedGames.map((o) => o.value);

Et voilà, stable sorting in our table. Again, this would have been a whole lot easier if JavaScript just had stable sorting built in — but given that it doesn't, this is the easiest we get away with.

We can also write this as a single chain of map-sort-map:

games = games
    .map((value, index) => ({ value, index }))
    .sort(compareByPropertyStable("year"))
    .map((o) => o.value);

(The pattern used above is known in the Perl world as a Schwartzian transform.)

In this case the assignment is necessary, because map generates fresh arrays.

Summary

And we're done! Summarizing a bit:

  • JavaScript expects you to provide compare functions when you want anything other than lexicographic order.
  • There's a very specific way you have to write the compare functions.
  • Instead of writing them out by hand every time, it's shorter, cleaner, safer, and more enjoyable to define (or import) a small number of utility functions (compareBy, property, chained) so that we can functionally compose the compare function we want.
  • JavaScript's specification and implementations don't guarantee stable sort in general.
  • Instead, if you want stable sort (as one often does), you have to write your compare functions to take that into account.
  • Even this can be made practical and pleasant by composing functions.

Afterword: a cute DSL

As I was doing research for this post, it struck me that someone might have addressed the same pain points already out in the npm ecosystem. And sure enough, I found the comparators module, which is based on Java 8's API and allows us to sort our games like this:

games.sort(Comparators.comparing("publisher").thenComparing("title"));

In this case, we're sending strings into the comparing methods, but sending an arbitrary selector function works also according to the API. The secret sauce that makes the above work — very JavaScript-y — is that the compare function returned from Comparators.comparing has been adorned with a .thenComparing method.

Afterword: ES2019

Starting with the 2019 edition of the EcmaScript standard, sorting is guaranteed to be stable. Yay!

Be aware though that this does not change the fact that for many more years, there will be older implementations out there on people's computers and devices that do not use a stable sort. So for backwards compatibility for the forseeable future, the advice in this article still very much holds.

JavaScript har en .sort-metod, men denna metod har ett antal vassa hörn. Den här artikeln förklarar hur man kan lära sig att leva med sortering i JavaScript.

Den uråldriga konsten att arrangera element

Här är .sort-metoden:

> ["banana", "coconut", "apple"].sort()
["apple", "banana", "coconut"]

Lätt som en plätt! Som du ser ovan så returnerar .sort() det sorterade resultatet.

Men, som en TV-shop-snubbe skulle säga, det är inte allt! Istället för att ge dig en ny array med elementen sorterade så är JavaScripts sorteringsmetod "in-place" — det använder arrayen som du skickade in för att arrangera om elementen.

> let fruits = ["banana", "coconut", "apple"]
> fruits.sort()
> // the array `fruits` is now sorted: `["apple", "banana", "coconut"]`

Du läste rätt. JavaScripts .sort() både modifierar arrayen, och returnerar den.

På grund av detta så är det lite dålig stil att tilldela resultatet av sorteringen tillbaka till originalarrayen:

> fruits = fruits.sort();     // gör inte detta!

Det är inte fel som sådant, det är bara redundant, lite som att laga sin middag en extra gång när den redan är färdiglagad. Mitt råd är att aldrig tilldela i samband med .sort(). (Att kedja sorteringar är OK, eftersom vi har att göra med samma array-referens hela tiden. Men det är fel på grund av bristen på stabilitet; se senare i artikeln.)

Det är också viktigt i kontexter som kräver oföränderlighet ("immutability") att komma ihåg at .sort() pajar den ursprungliga arrayen; om det inte är acceptabelt så kan man klona arrayen innan man sorterar:

> let sortedFruits = [...fruits].sort();

Matte är svårt, låt oss gå och shoppa

Eftersom vi hade en så enastående framgång med frukter så fortsätter vi genast till tal:

> [1, 2, 17, 24, 123, 1024].sort()
[1, 1024, 123, 17, 2, 24]

Åh nej! JavaScripts svar ränner upp mot våra fasta övertygelser om ordningen hos talen på tallinjen!

Vad är det som händer här? Anledningen till att frukterna kom ut i rätt ordning men att talen inte gjorde det är att JavaScripts sortering är lexikografisk om inget annat anges. Den jämför allt som strängar — och mycket riktigt, "1024" skulle uppträda någonstans mellan "1" och "123" i en (i sanning enorm) ordbok av tal.

(Nu rustar en legion av upprörda läsare upp för att maila mig om det omöjliga i att ställa alla reella tal i ordning i en ordbok. Kära hypotetiska ilskna läsare, var lugna. Vi pratar endast om att placera alla IEEE 754-dubbelprecisionsflyttal i en ordbok. Det är fortfarande väldigt dumt, men definitivt görbart.)

Innan vi tittar på hur man ska fixa numerisk sortering kan vi fråga oss varför defaulten är lexikografisk ordning. Jag tror att det finns två relaterade skäl:

  • JavaScript, i egenskap av "löst typat" språk, ser inte "array av strängar" eller "array av tal"; det ser bara "array". I någon mening så måste det bestämma sig för en default-sorteringsordning utan att veta någonting om typen på arrayens element.

  • Om vi behövde besluta oss för en sorteringsordning som funkar på allt, inklusive heterogena arrayer som innehåller en mix av olika typer, då är lexikografisk ordning svaret. Detta baseras på den djupa teorin om "allting kan konverteras till en sträng, hur illa resultatet än må bli".

Att fixa numerisk sortering

Som MDN-sidan för Array.prototype.sort påpekar så accepterar .sort()-metoden en frivillig compareFunction-parameter. Det är så här vi ger oss in i spelet med att ange ordningen, till exempel numerisk ordning.

function compareNumerically(a, b) {
    if (Number(a) < Number(b)) {
        return -1;
    } else if (Number(a) > Number(b)) {
        return +1;
    } else {
        return 0;
    }
}

En jämförelsefunktion som den ovan lovar att hålla sig till ett protokoll, nämligen att returnera -1, 0, eller +1 beroende på den relativa ordningen mellan sina två parametrar. (Det är tillåtet att returnera vilka positiva eller negativa tal som helst, men det behöver man sällan göra.) -1 betyder "a är mindre än b", 0 betyder "a och b sorteras lika", +1 betyder "a är större än b".

Men det slutar inte där. .sort()-metoden förväntar sig att jämförelsefunktionen ska vara konsistent, och returnera samma output givet samma inputs. Det förväntar sig också att jämförelsefunktionen anger en linjärordning, alla element kan placeras i samma ordning på en linje i stil med tallinjen. (Det är OK för värden att betraktas som lika av jämförelsefunktionen även när de inte är identiska. Mer om detta nedan.)

Om du frågar mig så tycker jag att värdena -1, 0, +1 är en smula magiska och oförklarade. De tillhör en svunnen tid när sådana protokoll ansågs gulliga och att känna till dem var en del av att höra till en ingrupp av kamp-ärrade programmerare. Vi kan bättre genom att namnge konstanterna för vad de representerar:

const LESS = -1, EQUAL = 0, GREATER = +1;

function compareNumerically(a, b) {
    if (Number(a) < Number(b)) {
        return LESS;
    } else if (Number(a) > Number(b)) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

Nu fungerar den numeriska sorteringen:

> [1, 2, 17, 24, 123, 1024].sort(compareNumerically)
[1, 2, 17, 24, 123, 1024]

En snabb sidogrej: eftersom vi får lov att returnera vilka positiva eller negativa tal som helst från jämförelsefunktionen, så skulle den här kortare versionen också fungera:

function compareNumerically(a, b) { return a - b }

Men som vi kommer att se nedan så får vi fler fördelar i den här artikeln genom att hålla oss kvar vid den längre, mer explicita implementationen.

Att jämföra på en property

Låt oss säga, helt hypotetiskt, att jag har så många datorspel hemma att jag behöver hålla reda på dem i en liten databas och visa dem i en tabell på en webbsida. Ett spel representeras av följande klass:

class Game {
    constructor(title, publisher, year) {
        this.title = title;
        this.publisher = publisher;
        this.year = year;
    }
}

Kom ihåg, det här handlar om hundratals spel. Helt hypotetiskt. Om vi har en array av spel, hur kan vi sortera dem på ett vettigt sätt?

Uppmuntrade av vår framgång med talen definierar vi en sorteringsfunktion för var och en av properties på Game-objekt:

function compareByTitle(a, b) {
    if (a.title < b.title) {
        return LESS;
    } else if (a.title > b.title) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

function compareByPublisher(a, b) {
    if (a.publisher < b.publisher) {
        return LESS;
    } else if (a.publisher > b.publisher) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

function compareByYear(a, b) {
    if (a.year < b.year) {
        return LESS;
    } else if (a.year > b.year) {
        return GREATER;
    } else {
        return EQUAL;
    }
}

Uj! Det var mycket kod. Inte bara det, det var mycket repetitiv kod. Det är typ den värsta sorten.

Om vi kisar lite på de tre funktionerna så ser vi att de alla gör samma sak, men med olika properties. Det vill säga, vi kan faktorisera ut "jämför på property"-delen från den delen som anger en specifik property. Här, låt oss göra en funktion som returnerar en skräddarsydd jämförelsefunktion:

function compareByProperty(p) {
    return (a, b) => {
        if (a[p] < b[p]) {
            return LESS;
        } else if (a[p] > b[p]) {
            return GREATER;
        } else {
            return EQUAL;
        }
    };
}

Nu kan då våra tre jämförelsefunktioner definieras superlätt; den sköna belöningen för att hålla saker torra ("DRY", "Don't Repeat Yourself"):

let compareByTitle = compareByProperty("title");
let compareByPublisher = compareByProperty("publisher");
let compareByYear = compareByProperty("year");

Det är najs, men vi kan gå ett steg längre. Vi kan faktorisera ut "jämför på"-delen från "property"-delen! Skåda:

function compareBy(fn) {
    return (a, b) => {
        if (fn(a) < fn(b)) {
            return LESS;
        } else if (fn(a) > fn(b)) {
            return GREATER;
        } else {
            return EQUAL;
        }
    };
}

function property(p) {
    return (e) => e[p];
}

Våra propertyjämförelsefunktioner ser nu ut så här:

let compareByTitle = compareBy(property("title"));
let compareByPublisher = compareBy(property("publisher"));
let compareByYear = compareBy(property("year"));

Vad tjänade vi på denna sista faktorisering? compareBy-funktionen är mer generell, och kan svälja compareNumerically-funktionen som vi med möda definierade ovan:

let compareNumerically = compareBy(Number);

Det är fint när saker blir enklare! Och det "läser" fint också. "Compare by Number"; "Jämför på tal".

Att göra samma sak med andra wrapper-typer skulle också fungera: compareBy(Boolean), och compareBy(String). Återigen, den sistnämnda är defaulten, så vi behöver inte ange den om vi inte vill vara explicita.

Om vi tar ett steg tillbaka, det här är trevligt eftersom det bättre stämmer överens av vår intuition om sortering. Konventionen med en jämförelsefunktion med -1, 0, och +1 är flexibel men inte intuitiv. Ofta är tanken vi vill uttrycka "jämför baserat på någonting som vi kan beräkna från varje element". Detta är var compareBy gör. Java 8 lägger till en statisk metod Comparator.comparing som också gör precis detta.

Väldigt stabilt geni

Jag behöver visa mina spel i en bra förutsägbar ordning på sidan. Låt oss säga att jag vill ordna dem främst enligt publicist, men inom varje publicist vill jag sortera dem på titel. Så problemet är "sortera på publicist och sedan (om det finns spel med samma publicist) på titel".

Kan vi göra detta i JavaScript? Svaret är förstås ja, men JavaScript ger sig den på att göra det svårt för oss.

En hyggligt klipsk sak vi kan prova är att sortera två gånger:

games.sort(compareByTitle)
     .sort(compareByPublisher);  // not: GÖR EJ SÅ -- se förklaring nedan

Notera det bakvända tänket här: eftersom vi vill ha spelen primärt sorterade på publicist så gör vi den sorteringen sist. Detta resonemang är märligt men korrekt.

För att detta ska kunna funka, måste den andra sorteringen respektera och bibehålla den sorterade-på-titel-ordningen från den första sorteringen, i alla de fall då den jämför två spel av samma publicist. Det vill säga, om compareByPublisher säger att resultatet är EQUAL så måste .sort() säga "bra, så behåller jag ordningen som den redan är".

En sorteringsalgoritm som gör detta kallas stabil. Det är inte en tautologisk egenskap — en sorteringsalgoritm kan också vara instabil, i vilket fall den inte ger några garantier om den slutliga ordningen hos element som jämför EQUAL (och med största sannolikhet förstör den ordningen).

Så... frågan blir, är JavaScripts sortering garanterat stabil?

Och svaret, som du redan misstänkte illa till mods i maggropen, är nej. Det vore vansinnigt användbart för oss att kunna anta en stabil sortering. Men med JavaScripts inbyggda .sort() så kan man inte anta det. JavaScript är många saker, men det är inte din bästa vän.

Vi talar ofta om JavaScript, men i själva verket finns det många implementationer av JavaScript ute i världen. För närvarande finns dessa större implementationer:

  • v8 (Chrome, Node.js) — instabil sortering
  • JavaScriptCore (Safari) — stabil sortering
  • SpiderMonkey (Firefox) — stabil sortering
  • ChakraCore (Edge) — stabil sortering

I v8 är sortering instabil. I alla övriga stora browsers är sortering stabil. (I äldre versioner av Firefox och Opera så brukade sortering vara instabil.) Om vi vill att vår kod ska fundera samma tvärsöver alla browsers, gamla och nya, så kan vi inte förutsätta stabil sortering.

(Faktum är att situationen med v8 är mer detaljerad än så. Om ens array råkar innehålla 10 element eller färre, kommer sorteringen att vara stabil, eftersom v8 faller tillbaka på "insertion sort" av prestandaskäl, och insertion sort är stabil! Så man får en stabil sortering ibland, för den typen av korta listor man troligen använder i testfall.)

Ok, så glöm implementationer. Vad har ECMAScript-specifikationen att säga om sorteringars stabilitet? Kanske vi kan tvinga ned specifikationen i halsen på implementatörerna?

Elementen i denna array är sorterade. Sorteringen är inte nödvändigtvis stabil [...]

Tydligen inte. Tack för ingenting, ECMAScript-specifikationen!

Förresten så är JavaScript i ganska gott sällskap här. Vissa språk (Java, Python) har en inbyggd biblioteksfunktion för sortering som garanterar stabilitet, medan andra språk (Ruby, C#) har en som inte garanterar det. Det verkar vara kopplat till det faktum att historiskt sett så har det inte funnits ett bra sätt att få Quicksort både stabil och maximalt snabb. Stabilitet offrad för prestanda.

Att fixa stabil sortering

Hur kan man göra sorteringen stabil? Vad vi behöver är en "kedjad" jämförelsefunktion som gör vad stabil sortering borde ha gjort åt oss automatiskt: den jämför på publicist först, och om dessa jämför lika faller den tillbaka på att jämföra på titel:

function compareByPublisherThenTitle(a, b) {
    if (a.publisher < b.publisher) {
        return LESS;
    } else if (a.publisher > b.publisher) {
        return GREATER;
    } else {
        if (a.title < b.title) {
            return LESS;
        } else if (a.title > b.title) {
            return GREATER;
        } else {
            return EQUAL;
        }
    }
}

Visuellt ser den koden ut som en jämförelsefunktion upptryckt i en annan. Och ja, den fungerar:

> games.sort(compareByPublisherThenTitle);

Men vi kan helt klart göra bättre ifrån oss, i termer av att faktorisera ut gemensamma lösningar. Hur vore det om vi hade en "kedjad compare" som kan koordinera mellan två compare-funktioner, och faller tillbaka på den andra om den första returnerar EQUAL?

function chained(fn1, fn2) {
    return (a, b) => {
        let v = fn1(a, b);
        return v === EQUAL
            ? fn2(a, b)
            : v;
    };
}

Nu kan vi använda denna kedjningsmekanism istället för att manuellt skriva en monstruös kombinerad jämförelsefunktion:

let compareByPublisherThenTitle = chained(compareByPublisher, compareByTitle);

Eller, om vi vill:

let compareByPublisherThenTitle = chained(compareBy(property("publisher")), compareBy(property("title")));

Stabil sortering på en existerande array

Ovanstående fungerar fint för de fall när vi inte bryr oss om den existerande ordningen på elementen. Men vi kan också föreställa oss scenarior när vi bryr oss om det.

Tänk till exempel på om spelen visas i en tabell på sidan, och tabellen har klickbara kolumnhuvuden "titel", "publicist", och "år". När man klickar på ett kolumnhuvud så kan man sortera spelen baserat på den propertyn.

Förstås önskar vi att den här sorteringen ska vara stabil också; det vill säga, vilken ordning som nu redan existerar bland tabellraderna bör bibehållas när det är möjligt. I det här fallet agerar JavaScripts instabila sortering maximalt mot oss, och vi måste vara kreativa.

För att bibehålla den existerande ordningen skulle vi vilja försätta oss i en situation där vi kan skriva compareBy(property("index")), där index-propertyn innehåller array-indexet på elementet. Tyvärr finns ingen sådan index-property generellt... så vad nedanstående kod gör är att temporärt lägga till en sådan property innan sorteringen, och sedan plocka bort den efteråt.

let indexedGames = games.map((value, index) => ({ value, index }));
let compareByPropertyStable = (p) => chained(compareBy((e) => e.value[p]), compareBy(property("index")));
indexedGames.sort(compareByPropertyStable("year"));     // till exempel
games = indexedGames.map((o) => o.value);

Och voilà, stabil sortering i vår tabell. Återigen, det hela hade varit så mycket enklare om JavaScript bara hade stabil sortering inbyggd — men eftersom det inte har det, så är det här det enklaste vi kommer undan med.

Vi kan också skriva det hela som en enda kedha av map-sort-map:

We can also write this as a single chain of map-sort-map:

games = games
    .map((value, index) => ({ value, index }))
    .sort(compareByPropertyStable("year"))
    .map((o) => o.value);

(Mönstret som används ovan kallas i Perlvärlden för en Schwartzisk transform.)

I den här fallet är tilldelningen nödvändig, eftersom map producerar fräscha arrayer.

Sammanfattning

Vi är i mål! Låt oss sammanfatta lite:

  • JavaScript förväntar sig jämförelsefunktioner när man önskar något annat än lexikografisk ordning.
  • Dessa skrivs på ett väldigt specifikt sätt.
  • Istället för att skriva dem för hand varje gång är det kortare, renare, säkrare, och mer njutbart att definiera (eller importera) en liten uppsättning hjälpfunktioner (compareBy, property, chained) så att vi funktionellt kan sätta samman den jämförelsefunktion vi är intresserade av.
  • JavaScripts specifikation och implementationer garanterar inte en stabil sortering i allmänhet.
  • Istället, om man vill ha en stabil sortering (vilket man ofta vill) måste man skriva sin jämförelsefunktion för att ta hänsyn till detta.
  • Även detta kan göras praktiskt och behagligt genom att sätta samman funktioner.

Addendum: ett sött domänspecifikt språk

När jag gjorde efterforskningar för den här artikeln slog det mig att någon redan kan ha adresserat samma problem redan i npm-ekosystemet. Och mycket riktigt så hittade jag comparators-modulen, som tar avstamp från Java 8:s API och låter oss sortera våra spel så här:

games.sort(Comparators.comparing("publisher").thenComparing("title"));

I det här fallet skickar vi stängar till comparing-metoderna, men enligt API:t fungerar det även att skicka godtyckliga selektorfunktioner. Den hemliga såsen som får ovanstående att fungera — väldigt JavaScriptigt — är att jämförelsefunktionen som returneras från Comparators.comparing har utsmyckats med en .thenComparing-metod.

Addendum: ES2019

Från och med 2019 års utgåva av EcmaScript-standarden så är sortering garanterat stabil. Hurra!

Men var medveten om att detta inte ändrar det faktum att det i många år kommer att finnas äldre implementationer därute på folks datorer och enheter som inte sorterar stabilt. Så av bakåtkompatibilitetsskäl för överskådlig framtid så gäller råden i den här artikeln fortfarande.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment