Can a Non-Stable JavaScript Sort Become Stable?

Stable Sorting in JavaScript with a Twist

Sorting a collection of objects is a common task in programming, often requiring stability to preserve the original order of equal elements. However, stability may not be inherent in the sorting algorithm employed.

Introducing a Stable Non-Stable Sort

A surprising yet effective approach involves transforming a non-stable sorting function into a stable one. Before sorting, the positions of all elements are obtained. The sorting condition is modified to consider both the primary key and the element's original position as a secondary key.

By utilizing the position as a tiebreaker in comparison, the stability of the final sorted result is ensured.

Implementation in JavaScript

The snippet below provides an example implementation in JavaScript:

<code class="javascript">function stableSort(array, key) {
  const positions = [];

  for (let i = 0; i < array.length; i++) {
    positions[i] = i;
  }

  array.sort((a, b) => {
    const keyComparison = a[key].localeCompare(b[key]);
    return keyComparison || positions[a] - positions[b];
  });
}</code>

In this code, the stableSort function sorts the array by the specified key in a stable manner. The positions array captures the initial positions of the elements. The sorting condition relies on localeCompare for string comparisons and falls back to the position comparison as a tiebreaker.

This approach offers the flexibility to leverage any non-stable sorting algorithm while maintaining stability for equal elements.

The above is the detailed content of Can a Non-Stable JavaScript Sort Become Stable?. For more information, please follow other related articles on the PHP Chinese website!