質問

リストがどの程度ソートされているかを測定する方法はありますか？

つまり、リストがソートされているかどうか（ブール値）を知るのではなく、統計学における相関係数のような、"sortness"の比率のようなものを知りたいのです。

例えば

• リストの項目が昇順であれば、そのレートは1.0となります。

• リストが降順にソートされている場合、そのレートは-1.0となります。

• リストがほぼ昇順の場合、そのレートは0.9または1に近い値になります。

• リストが全くソートされていない場合（ランダム）、そのレートは0に近いでしょう。

練習用にScalaで小さなライブラリを書いています。ソートレートがあれば便利だと思うのですが、そのような情報は見当たりません。多分、私がその概念に対する適切な用語を知らないのだろう。

どのように解決するのですか？

単純にリストの中の反転数を数えればいいのです。

反転

型の要素列の反転。 T は、ある順序に従って順序が逆転して現れるシーケンス要素のペアです。 < のセットで T 's.

から ウィキペディア :

形式的には、次のようにします。 A(1), A(2), ..., A(n) の列である。 n の数値が表示されます。

もし i < j と A(i) > A(j) であれば、ペアの (i,j) と呼ばれます。 反転 の A .

は 反転数 は、配列の並び順を表す一般的な尺度の一つです。

形式的には、反転数は反転の数、と定義される。

これらの定義をより明確にするために、シーケンスの例を考えてみましょう。 9, 5, 7, 6 . このシーケンスは 逆さ (0,1), (0,2), (0,3), (2,3) と、その 反転数 4 .

の間の値が必要な場合 0 と 1 で割ると、反転数 N choose 2 .

このリストの並び順のスコアを計算するアルゴリズムを実際に作るには、2つのアプローチがあります。

アプローチ1 (決定論的)

お気に入りのソートアルゴリズムを、実行中に何回反転を修正したかを追跡できるように修正する。これは自明ではなく、選択したソートアルゴリズムによって実装が異なりますが、最終的には、最初に使用したソートアルゴリズムよりも（複雑さの点で）高価ではないアルゴリズムが完成します。

この方法を取る場合、"swaps."を数えるほど単純ではないことに注意してください。例えば、Mergesortは最悪の場合 O(N log N) しかし、降順でソートされたリストに対して実行すると、すべての N choose 2 を反転させます。 それは O(N^2) で反転を修正しました。 O(N log N) の操作になります。 そのため、いくつかのオペレーションは、必然的に一度に複数の反転を修正する必要があります。実装には注意が必要です。 注意：これを行うには O(N log N) 複雑で、厄介です。

関連する 順列の「逆順」の数を計算する

アプローチ2（ストキャスティック）

• ランダムなペアのサンプリング (i,j) ここで i != j
• 各ペアについて、以下を判定します。 list[min(i,j)] < list[max(i,j)] (0または1)
• これらの比較の平均を計算し、次式で正規化する。 N choose 2

個人的には、厳密性が要求されない限りは、ストキャスティック・アプローチを採用したいですね。

本当に欲しいものが値であれば ( z' の間にある -1 (降順でソート)から 1 (昇順) にすると、上の値を単純にマッピングできます ( z の間にある) 0 (昇順)と 1 (降順)を、この式でこの範囲に変換します。

z' = -2 * z + 1