1

タイプが実装されIComparable<T>ていて、100個の要素を持つこのタイプのコレクションがある場合。このコレクションでSortメソッドを呼び出すと、メソッドは何回CompareTo呼び出され、どのように呼び出されますか？このように使用されますか？

CompareTo(item0, item1);
CompareTo(item1, item2);
CompareTo(item2, item3);
CompareTo(item3, item4);
...
CompareTo(item97, item98);
CompareTo(item98, item99);

編集：基本的に私がやろうとしているのは、この並べ替え方法を値ベースの並べ替えに変えて、各アイテムに値を割り当ててから並べ替えることです。説明するのは難しいですが、この問題に-1,0,1ベースのソート機能を使用することはできません。しかし、私が持っているのは、アイテムを並べ替えるために使用する必要があるCompareTo関数だけです。したがって、アイテムごとにいくつかの値を生成する必要があります。そうすると、プログラムはそれらを最小値から最大値に並べ替えます。

4

2 に答える 2

11

データに依存するため、（ほとんどの並べ替えアルゴリズムでは）100％確実にすることはできません。たとえば、特定の並べ替えアルゴリズムは、データのN（Nはコレクションのサイズ）の比較のみを実行しますが、そうでない場合はさらに多くのデータを並べ替える必要があります。

MergeSort、QuickSort、HeapSortなどの一般的に使用される並べ替えアルゴリズムはすべてO（n * log（n））です。つまり、比較の数は、アイテムの数にログベースのログベースを掛けたもののオーダーになります。アイテムの数。（これらのアルゴリズムの対数ベースは2になります。）これは正確ではありませんが、その関係に応じてスケーリングされます。

特定の並べ替え操作で何回呼び出されるかに興味がある場合は、次のようなものを使用できます。

public class LoggingComparer<T> : IComparer<T>
{
    private IComparer<T> otherComparer;
    public LoggingComparer(IComparer<T> otherComparer)
    {
        this.otherComparer = otherComparer;
    }

    public int Count { get; private set; }

    public int Compare(T x, T y)
    {
        Count++;
        return otherComparer.Compare(x, y);
    }
}

別の比較子をラップしますが、比較呼び出しの数もカウントします。使用例は次のとおりです。

var list = new List<int>() { 5, 4, 1, 2, 3, 8, 7, 9, 0 };

LoggingComparer<int> comparer = new LoggingComparer<int>(Comparer<int>.Default);
list.Sort(comparer);
Console.WriteLine(comparer.Count);
于 2012-12-06T21:56:08.013 に答える
1

Servyの答えを支持するピギー。ソートアルゴリズムの比較操作の漸近的複雑さが何であれ、それはCompareTo（）に対して行われる可能性のある呼び出しの数です。これは通常、成長パターンであり、正確な操作数ではないことに注意してください。

于 2012-12-06T21:57:25.240 に答える