67

ECMAスクリプトの仕様では、配列の並べ替えに使用するアルゴリズムが指定されておらず、並べ替えが安定しているかどうかも指定されていないことを知っています。

Firefoxでこの情報が見つかりました。これは、firefoxが安定ソートを使用することを指定しています。

IE 6/7/8、Chrome、Safariについて知っている人はいますか？

4

5 に答える 5

70

ES2019以降、sort安定している必要があります。ECMAScript 1st EditionからES2018では、不安定になることが許可されていました。

単純なテストケース（見出しを無視します。エンジンの並べ替えが安定している場合は、2番目の数字のセットは連続している必要があります）。注：このテストケースは、配列のサイズに基づいて並べ替えアルゴリズムを切り替えたChromeの一部のバージョン（技術的にはV8）では機能しません。小さな配列では安定した並べ替えを使用しますが、大きな配列では不安定な並べ替えを使用します。（詳細。）動作をトリガーするのに十分な大きさの配列を作成する変更バージョンについては、質問の最後を参照してください。

IEの並べ替えは、私がこれまで使用したことがある限り安定しています（つまり、IE6）。IE8で再度確認すると、まだ当てはまるようです。

リンク先のMozillaページには、Firefoxの種類は安定していると書かれていますが、Firefox 2.0より前（およびそれを含む）は必ずしもそうではなかったと私は断言します。

いくつかの大雑把な結果：

  • IE6 +：安定
  • Firefox <3：不安定
  • Firefox> = 3：安定
  • Chrome <70：不安定
  • Chrome> = 70：安定
  • Opera <10：不安定
  • Opera> = 10：安定
  • Safari 4：安定
  • エッジ：長い配列（> 512要素）では不安定

Windowsでのすべてのテスト。

参照： javascriptでの高速で安定したソートアルゴリズムの実装

このテストケース（ここから変更）は、アレイに「より効率的な」ソート方法を選択するのに十分なエントリがあることを確認することにより、V8（たとえば、ノードv6、Chrome <v70）の問題を示します。これは非常に古いJavaScriptエンジンを念頭に置いて書かれているため、最新の機能はありません。

function Pair(_x, _y) {
    this.x = _x;
    this.y = _y;
}
function pairSort(a, b) {
    return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
    check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
    var entry = check[i];
    var found = min[entry.x];
    if (found) {
        if (found.y > entry.y) {
            console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
            ++issues;
        }
    } else {
        min[entry.x] = {x: entry.x, y: entry.y, i: i};
    }
}
if (!issues) {
    console.log("Sort appears to be stable");
}

于 2010-06-12T06:14:51.827 に答える
15

C /C++で日常的に使用しているトリックを共有したいと思いますqsort()。

JSのsort（）を使用すると、比較関数を指定できます。同じ長さの2番目の配列を作成し、0から増加する数で埋めます。

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

これは、元の配列へのインデックスです。2番目の配列を並べ替えます。カスタム比較関数を作成します。

  indicies.sort(function(a, b)) {

2番目の配列から2つの要素を取得します。これらを元の配列へのインデックスとして使用し、要素を比較します。

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

要素がたまたま等しい場合は、それらのインデックスを比較して順序を安定させます。

   if (a < b)
     return -1;
   else
     return 1;
  });

sort（）の後、2番目の配列には、安定したソート順で元の配列の要素にアクセスするために使用できるインデックスが含まれます。

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

一般に、安定したソートアルゴリズムは成熟しつつあり、古き良きqsortと比較してより多くの追加メモリを必要とします。だからこそ、安定ソートを義務付けているスペックはほとんどないのだと思います。

于 2010-06-11T23:10:18.687 に答える
10

V8v7.0およびChrome70の時点で、Array.prototype.sort実装は安定しています。

以前は、V8は10個を超える要素を持つ配列に不安定なQuickSortを使用していました。現在、V8は安定したTimSortアルゴリズムを使用しています。

まだ不安定な実装を持っている唯一の主要なエンジンJavaScriptエンジンはArray#sort、MicrosoftEdgeで使用されているChakraです。Chakraは、512を超える要素を持つ配列にQuickSortを使用します。小さい配列の場合は、安定した挿入ソートの実装を使用します。

デモ： https ：//mathiasbynens.be/demo/sort-stability

于 2018-09-03T14:40:38.320 に答える
0

誰かがそれが役に立つと思う場合に備えて、私はこれのためにポリフィルを持っていましたが、今はそれを削除しています：

const stable = (count => {
    const
        array = new Array(count),
        buckets = {};

    let i, k, v;

    for (i = 0; i < count; ++i) {
        array[i] = [Math.floor(Math.random() * 3) + 1, i + 1];  // [1..3, 1..count]
    }

    array.sort((a, b) => a[0] - b[0]);

    for (i = 0; i < count; ++i) {
        [k, v] = array[i];

        if (buckets[k] > v) {
            return false;
        }

        buckets[k] = v;
    }

    return true;
// Edge's JS engine has a threshold of 512 before it goes unstable, so use a number beyond that:
})(600);

if (!stable) {
    const
        { prototype } = Array,
        { sort } = prototype;

    Object.defineProperty(prototype, 'sort', {
        configurable : true,

        value(sortFn) {
            const
                array = this,
                len = array.length,
                temp = new Array(len);

            let i;

            for (i = len; i-- > 0; /* empty */) {
                temp[i] = i;
            }

            sortFn = sortFn || defaultSort;

            sort.call(temp, (index1, index2) => sortFn(array[index1], array[index2]) || index1 - index2);

            // we cannot do this directly into array since we may overwrite an element before putting it into the
            // correct spot:
            for (i = len; i-- > 0; /* empty */) {
                temp[i] = array[temp[i]];
            }

            for (i = len; i-- > 0; /* empty */) {
                array[i] = temp[i];
            }

            return array;
        }
    });
}

于 2021-01-05T14:05:33.120 に答える
-2

非ネイティブの並べ替えアルゴリズムを利用する必要があるブラウザのリストを探している場合、私の提案はそうではありません。

代わりに、スクリプトがロードされたときにソートの健全性チェックを実行し、そこから決定を下します。

仕様はその点で特定の動作を必要としないため、同じブラウザライン内であっても、後の変更の影響を受けません。

http://www.browserscope.org/にパッチを送信して、そのようなテストをスイートに含めることができます。ただし、機能の検出はブラウザの検出よりも優れています。

于 2010-06-11T23:04:42.997 に答える