いいえ、それはクラスからの質問ではありません。私は自分でツリーとヒープ (部分的にソートされたバイナリ ツリー) を研究しており、一般的なデータ構造に関連してこの 2 つのプロパティ/アクションを正しく定義する方法を考えていました。
9 に答える
非常に大まかに言えば、順序付けは、ある順序でどの要素を他のどの要素の前に並べるべきかを指定します。並べ替えは、そのような要素のコレクションを、順序付けによって指定された順序に並べるプロセスです。
(少し紛らわしいことに、要素のシーケンスを「順序付け」することについて話すこともできます。これは、順序付けによって指定された順序にそれらをソートすることと同じことを意味します。)
アップデート:
実装の観点から言えば、良い例は標準コンテナー (例: map、http://en.cppreference.com/w/cpp/container/map ) で、順序付けを提供する追加のテンプレート パラメーターを使用します。std::less<Key>
これは、マップの場合のデフォルトです。独自の順序付けが必要な場合は、マップを作成するときに別のコンパレータ タイプを使用すると、代わりにそれが使用されます。独自のコンパレータを提供する一般的な方法は、bool operator()(const Key& lhs, const Key& rhs) const
.
IBM は、ソート済みセットと順序付きセットを区別しています。
セットはソートまたは順序付けできます。
順序付きセットは、要素がセットに追加された順序で配置されているセットです。これがデフォルトでセットが作成される方法であることに注意してください。例えば:
{int} S1 = {3,2,5};
と
ordered {int} S1 = {3,2,5};
同等です。
ソート済みセットは、要素が自然な昇順 (または降順) で配置されているセットです。文字列の場合、自然順序は辞書式順序です。自然順序は、システム ロケールにも依存します。例えば:
sorted {int} sortedS = {3,2,5};
と
ordered {int} orderedS = {2,3,5};
は同等であり、sortedS または OrderedS を反復しても同じ動作になります。降順を指定するには、キーワード reversed を追加します。
また、National Information Assurance Partnershipは、2002 年に National Institute of Standards and Technology に用語の解釈を提案しました。
問題:
「ソート」と「順序付け」という用語の違いは何ですか? 時々、言葉は同じ意味で使われます。
声明
「並べ替え」と「順序付け」という用語は、IT システムの議論では同じ意味で使用されることがありますが、多少異なる意味を持っています。分類すると、アイテムをさまざまな種類またはクラスに分類します。注文すると、特定の順序でアイテムを配置します。
言葉としては、コンピューター コードのコンテキストではほぼ同義語です。例えば:
- SQL には
order by
句があるため、データ行は順序付けられます。 - Java には、
SortedSet
andSortedMap
インターフェース、インターフェースCollections.sort()
用のメソッドList
、およびArrays.sort()
配列用のメソッドがあります。
違いを特定するなら、配列またはjava.util.Listは順序付けられているがソートされていないと言うでしょう。
オブジェクトをarray
またはList
に配置すると、そこに配置された順序が保持され、インデックスでアクセスできますが、順序は任意であるため、ソートされません。
java.util.SortedSetを使用すると、好きな順序でオブジェクトを配置できます。これは、オブジェクトが java.util.Comparator の式または式によってソートされるためnatural ordering
です。ただし、インデックスで要素にアクセスすることはできません。これにより、それらはソートされますが、順序付けされません。
順序付けられたコレクションは、不揮発性で表示可能かつ再現可能なアドレスまたはその要素の相対的な位置の概念を意味します。 したがって、並べ替えは、任意の基準による要素の実際の配置です。
これを用語またはソートアルゴリズムで考えると役立つと思います。並べ替えアルゴリズムには、順序を保持するものと保持しないものがあります。たとえば、単純で非効率な 2 つの並べ替えアルゴリズム、バブル 並べ替えと選択並べ替えについて考えてみましょう。バブル ソートは順序を保持することが保証されていますが、選択ソートはそうではありません。順序を維持するとは、同一の要素が交換されないことを意味します。
特にアイテムにソートされていない他のデータが含まれている場合は、順序を維持することが重要です。たとえば、人々の年齢で並べ替える場合、年齢は同じでも名前が異なる可能性があり、元の順序を維持したい場合があります。
ウィキでソートアルゴリズムを参照してください。時間の複雑さと安定性が得られます。安定とは、元の順序が維持されることを意味します。
https://en.wikipedia.org/wiki/Sorting_algorithm
ランキング: セットの部分確定配置の比較。衝突が可能
rank1 = max({foo1.bar, foo2.bar})
rank2 = min({foo2.kite, foo2.kite})
順序付け: セットを潜在的な衝突なしに完全かつ一意に配置できるようにする加重ランキングの構成。挿入順序は、サブセットに対して明示的なランキングだけでは不十分な場合の代替解決策であることがよくあります
order = {
ordering1 = (foo1.bar != foo2.bar) ? rank1(foo1, foo2) : ordering2(foo1, foo2)
ordering2 = (foo1.kite != foo2.kite) ? rank2(foo1, foo2) : fallback(foo1, foo2)
}
ソート: 特定のアクセスおよび分割戦略を使用した順序によるセットの配置
sort1 = strand(foo, order)
sort2 = bubble(foo, order)
Sorted: 順序に応じたセットの配置のバイナリ状態 (true または false)
is_sorted = {
for (each foo)
(is_ordered(foo(n), foo(n-1)) ? continue : return false;
return true;
}