JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptのArray#sort()関数が内部で使用するソートアルゴリズムとは？

JavaScriptで配列を並べ替える際に使われるArray#sort()。しかし、その内部でどのようなソートアルゴリズムが動いているのか、正確に答えられる方は意外と少ないかもしれません。

実は、ECMAScript（JavaScript）の仕様では、Array.sortの実装に使用するアルゴリズムを特定していません。この点は実装者（各JSエンジンの開発元）に委ねられており、その結果、エンジンごとに異なるソートアルゴリズムが採用されています。

Mozilla（SpiderMonkey）の場合：マージソート

Mozillaが開発する「SpiderMonkey」JSエンジンでは、マージソート（mergeSort）が使用されています。実際の実装はC言語で書かれており、Mozillaの公式リポジトリでコードを確認できます。
参考：https://dxr.mozilla.org/seamonkey/source/js/src/jsarray.c

WebKit系エンジン（Chrome・Safariなど）の場合：状況に応じて使い分け

一方、WebKitベースのエンジン（Chrome、Safariなど）では、単一のアルゴリズムに固定せず、要素のデータ型や配列の長さに応じて最適なアルゴリズムを選択する方式を採用しています。

主な使い分けの例

  • 数値の配列： C++標準ライブラリのクイックソート（quick sort）関数を使用
  • 非数値の配列： マージソート（merge sort）を使用
  • その他のケース： 一部の条件では選択ソート（selection sort）も使用される

まとめ

Array#sort()がどのアルゴリズムで動作するかは、配列要素のデータ型とサイズによって変わるというのが答えです。パフォーマンスが重要な場面では、対象となるデータの特性と、利用しているJSエンジンの実装を意識しておくとよいでしょう。

  1. 最高のJavaScriptコンプレッサーはどれ？主要な圧縮ツールを徹底解説

    JavaScriptファイルのサイズは、Webサイトの表示速度やユーザー体験に大きな影響を与えます。コードを圧縮（ミニファイ）することで、不要な空白やコメントを取り除き、読み込み時間を大幅に短縮できます。ここでは、特におすすめのJavaScript圧縮ツールを紹介します。 Google Closure Compiler Google Closure Compilerは、Googleが提供する高機能なJavaScript最適化ツールです。単純な圧縮にとどまらず、JavaScriptを解析し、デッドコード（未使用のコード）を削除したうえで、残りのコードを書き換えて最小化します。その結果、実行速度の

  2. 【JavaScript】基準配列の順序どおりにオブジェクト配列をソートする方法

    JavaScriptでは、ある「文字列の配列」を基準として、別のオブジェクト配列をその順序どおりに並べ替えたい場面があります。本記事では、基準配列の順序に合わせてオブジェクト配列をソートする方法を、具体的なコード例とともにわかりやすく解説します。 やりたいこと まず、並べ替えの基準となる配列と、並べ替え対象のオブジェクト配列を用意します。各オブジェクトの content プロパティの値が、基準配列内の文字列に対応しています。 const order = [this, is, my, custom, order]; const myObjects = [ { id: 1, cont