Stable Sorting with JavaScript Arrays

Introduction

In this lab, we will explore the concept of stable sorting in JavaScript. Stable sorting is a technique that preserves the order of items in an array when their values are the same. We will use a function that utilizes the Array.prototype.map() and Array.prototype.sort() methods to implement stable sorting of an array.

Skills Graph

Stable Sort

To perform stable sorting of an array and preserve the initial indexes of items with the same values, follow these steps:

1. Open the Terminal/SSH and type node to start practicing coding.
2. Use Array.prototype.map() to pair each element of the input array with its corresponding index.
3. Use Array.prototype.sort() along with a compare function to sort the list while preserving the initial order if the items compared are equal.
4. Use Array.prototype.map() again to convert the array items back to their initial form.
5. The original array is not mutated, and a new array is returned instead.

Here's an implementation of the stableSort function in JavaScript:

const stableSort = (arr, compare) =>
  arr
    .map((item, index) => ({ item, index }))
    .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
    .map(({ item }) => item);

You can call the stableSort function with an array and a compare function to obtain a new array with the sorted items, as shown below:

const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const stable = stableSort(arr, () => 0); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Summary

Congratulations! You have completed the Stable Sort lab. You can practice more labs in LabEx to improve your skills.