これはしばらくの間私の心に残っている質問です...
アイテムのリストとそれらの同値関係があり、2つのアイテムの比較には一定の時間がかかるとします。アイテムのパーティション、たとえばリンクリストのリストを返したいのですが、それぞれに同等のアイテムがすべて含まれています。
これを行う1つの方法は、同等性をアイテムの順序付けに拡張し、それらを（並べ替えアルゴリズムを使用して）順序付けすることです。その後、すべての同等のアイテムが隣接します。
しかし、それはソートよりも効率的に行うことができますか？この問題の時間計算量は、並べ替えの時間計算量よりも低いですか？そうでない場合は、なぜですか？
あなたは一度に2つの異なる質問をしているようです。
1）同等性チェックのみを許可する場合、順序付けを行う場合よりもパーティション化が容易になりますか？答えはいいえだ。最悪の場合（たとえば、すべて異なる）のパーティショニングを決定するには、Omega（n ^ 2）の比較が必要です。
2）注文を許可する場合、分割は並べ替えよりも簡単ですか？答えは再びノーです。これは、要素の識別性の問題が原因です。つまり、すべてのオブジェクトが異なるかどうかを判断するには、Omega（nlogn）の比較が必要です。ソートはO（nlogn）時間で実行でき（Omega（nlogn）の下限もあります）、パーティションの問題を解決するため、漸近的に同じように困難です。
任意のハッシュ関数を選択する場合、等しいオブジェクトが同じハッシュを持つ必要はありません。その場合、それらをハッシュテーブルに配置することによって有用な作業を行うことはありません。
そのようなハッシュ（同じハッシュを持つことが保証されている等しいオブジェクト）を思いついたとしても、適切なハッシュの場合、時間計算量はO（n）と予想され、最悪の場合はOmega（n ^ 2）です。
ハッシュを使用するか並べ替えを使用するかは、質問で使用できない他の制約に完全に依存します。
他の答えも、あなたの質問が（主に）パーティショニングとソートの比較に関するものであることを忘れているようです！
アイテムのハッシュ関数と同値関係を定義できる場合は、ハッシュの計算が定数時間であると仮定して、線形時間でパーティションを実行できるはずです。ハッシュ関数は、同等のアイテムを同じハッシュ値にマップする必要があります。
ハッシュ関数がないと、パーティション化されたリストに挿入されるすべての新しいアイテムを、既存の各リストの先頭と比較する必要があります。その戦略の効率は、最終的にいくつのパーティションが存在するかによって異なります。
100個のアイテムがあり、最終的に3つのリストに分割されるとします。次に、各アイテムをリストの1つに挿入する前に、最大3つの他のアイテムと比較する必要があります。
ただし、これらの100個のアイテムが最終的に90個のリストに分割される場合（つまり、同等のアイテムが非常に少ない場合）、それは別の話です。これで、ランタイムは線形よりも2次に近くなります。
等価セットの最終的な順序を気にしない場合は、等価セットへの分割がより高速になる可能性があります。ただし、アルゴリズムと各セットの要素数によって異なります。
各セットにアイテムが非常に少ない場合は、要素を並べ替えてから、隣接する等しい要素を見つけることもできます。適切な並べ替えアルゴリズムは、n個の要素に対するO（n log n）です。
それぞれに多くの要素が含まれるセットがいくつかある場合は、各要素を取得して、既存のセットと比較できます。それらの1つに属している場合は追加し、そうでない場合は新しいセットを作成します。これはO（n * m）になります。ここで、nは要素の数、mは等価セットの数です。これは、大きいnと小さいmの場合はO（n log n）よりも小さくなりますが、mがnになる傾向があるため悪化します。 。
ソート/パーティション化アルゴリズムを組み合わせた方が速い場合があります。
比較ベースのソートには、通常、O（n log n）の下限があります。
アイテムのセットを反復処理し、それらを同じ比較値を持つアイテムのバケットに入れると仮定します。たとえば、リストのセット（ハッシュセットを使用するなど）に入れます。セットからリストのリストを取得した後でも、この操作は明らかにO（n）です。
---編集： ---
もちろん、これには2つの仮定が必要です。
したがって、パーティショニングの下限はO（n）です。
コンパレータを使用する必要がある場合、下限はソートまたはパーティショニングのΩ（n log n）比較です。その理由は、すべての要素を検査する必要がありますΩ（n）、コンパレータは各要素に対してlog n比較を実行して、その要素を他の要素との関係で一意に識別または配置する必要があります（各比較はスペースを2に分割し、スペースの場合はサイズnの場合、log nの比較が必要です。）
各要素を一定時間で導出される一意のキーに関連付けることができる場合、アリの分割をソートするための下限はΩ（n）です（RadixSortを参照） 。
一般に、パーティション化は並べ替えよりも高速です。各要素を、潜在的に同等の並べ替え済みの各要素と比較する必要がないため、パーティション化のすでに確立されているキーと比較するだけで済みます。基数ソートをよく見てください。基数ソートの最初のステップは、キーの一部に基づいて入力を分割することです。基数ソートはO（kN）です。データセットに指定された長さkで囲まれたキーがある場合は、基数ソートO（n）を使用できます。データが比較可能であり、境界キーがないが、セットを分割するための境界キーを選択した場合、セットの並べ替えの複雑さはO（n log n）になり、分割はO（n）になります。 。
これはデータ構造の典型的な問題であり、そうです、並べ替えよりも簡単です。また、各要素がどのセットに属しているかをすばやく検索できるようにする場合は、union-find操作とともに、互いに素なセットのデータ構造が必要です。ここを参照してください：http：//en.wikipedia.org/wiki/Disjoint-set_data_structure
ハッシュ関数を使用して不完全な可能性のあるパーティションを実行するために必要な時間は、O（n +bucketcount）[O（n *bucketcount）ではありません]になります。すべての衝突を回避するためにバケット数を十分に大きくすることはコストがかかりますが、ハッシュ関数がまったくうまく機能する場合は、各バケットに少数の個別の値があるはずです。統計的に独立した複数のハッシュ関数を簡単に生成できる場合は、キーがすべて最初のバケットと一致しない各バケットを取得し、別のハッシュ関数を使用してそのバケットの内容を分割できます。
各ステップでバケットの数が一定であると仮定すると、時間はO（NlgN）になりますが、バケットの数をsqrt（N）のように設定すると、パスの平均数はO（1）になります。各パスO（n）で動作します。