質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.51%
ECMAScript

ECMAScriptとは、JavaScript類の標準を定めるために作られたスクリプト言語です。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

1回答

2072閲覧

JavaScriptで、安定ソートをFeature Detectionできるのか

maisumakun

総合スコア145062

ECMAScript

ECMAScriptとは、JavaScript類の標準を定めるために作られたスクリプト言語です。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

6グッド

4クリップ

投稿2019/12/19 06:41

別な質問に回答する過程で調査していたところ、ES2019では、Array.prototype.sortが「The sort must be stable」となっていました(ECMA)。

とはいえ、そうでない過去のブラウザがある以上、この挙動に頼るには検証が必要となります。

…が、「ソートが安定である」ことをFeature Detectionする方法はありますでしょうか。

特定のパターンの配列で試して、実際に安定性が崩れていれば「安定でない」と結論付けられます。ただ、逆に何回やっても安定な結果が返ってきたとしても、それは「実行したデータ(あるいはその場面)に限ったこと」なのか「ソートが安定だと保証されている」のか区別が付きません。

そのような壁を超えて「安定性を確認する」ような方法がありましたら、ご提示いただれば幸いです。

tanat, d_96a, miyabi_pudding, p_p, oikashinoa, LouiS0616👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

少なくとも、通常のブラックボックステストで安定でないソートを確実に検出するのは不可能だと思います。

例えば、引数が 10 未満かどうかを返すだけの非常に単純な関数でさえ、

javascript

1const underTen = n => { 2 if (n === 5) return false; 3 return n < 10; 4}

のように実装されていると、ソースコードを見ない限り引数に 5 を指定したときのバグを検出することは困難です。

同様に、

javascript

1Array.prototype.sort = function() { 2 if (this が特定の値である) { 3 安定でないソートを行う 4 } else { 5 安定ソートを行う 6 } 7}

のように実装されていると、ソースコードを見ない限り安定でないソートを行うコード部分を実行させることは困難です。
特に、ソートでは複数のアルゴリズムを組み合わせて実装することが珍しくなく、データに合わせて条件分岐でアルゴリズムを切り替えていると思われるので、上記のコードほど極端ではないとしても似たコードになっていても不思議はありません。

なので、安定ソートで実装されているかを検証するためには、どうしてもソースコードを見る必要があると思います。

あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数は存在しないことの証明

理論上、あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数は存在しないと思われます。
停止性問題と同じ要領で以下のように証明できると思います。

もしも、あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数 isStable が存在すると仮定する。

javascript

1function isStable(sortFunction) { 2 if (sortFunction が常に安定ソートを行う) { 3 return true 4 } else { 5 return false 6 } 7}

ここで、配列をソートする mySort 関数を以下のように定義する。

javascript

1function mySort(array) { 2 if (isStable(mySort)) { 3 array を安定でないソートする 4 } else { 5 array を安定ソートする 6 } 7}

もしも、mySort が常に安定ソートを行うと仮定する。
その場合、isStable(mySort)true となる。
isStable(mySort)true のため、mySort の定義から mySort は安定でないソートを行う。
これは、mySort が常に安定ソートを行うという仮定に矛盾する。

もしも、mySort が安定でないソートを行うと仮定する。
その場合、isStable(mySort)false となる。
isStable(mySort)false のため、mySort の定義から mySort は常に安定でないソートを行う。
これは、mySort が安定でないソートを行うという仮定に矛盾する。

いずれにしろ矛盾するため、あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数 isStable は存在しない。

投稿2019/12/19 12:08

編集2019/12/21 13:46
2KOH

総合スコア999

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.51%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問