リストがソートされているとき、どのように言語*知っていますか？

Question

この質問がダムだと私に許してもらえますが、私にはそれが起こりました。どのように言語がソートされているかを知る方法がわかりません。

["Apple","Apricot","Blueberry","Cardamom","Cumin"] 

と私は"Cinnamon"を挿入したい：

は、私がリストを持っていると言います。 AFAIK私が使っている言語は、リストがソートされていることを知らない。単なるリストです。また、「ワイドスクリーン」の視野を持たないため、Aチャンクがどこで終了し、Cチャンクがリストの外側から始まるかはわかりません。そこで、各配列文字列の最初の文字と挿入文字列の最初の文字を比較します。挿入文字が大きい場合は、次の文字列に移動します。文字が一致すると、次の文字に移動します。次の文字列に移動し、配列のcharが挿入のcharより大きい場合、charがそこに挿入されます。

私の質問は、リストがソートされたときに知っている言語ですか？ ソートされていないソートされたリストを組み合わせるプロセスが同じで、リストが繰り返し処理されている場合、どのようにソート時間を節約できますか？

EDIT： 「ソートではソートに依存するアルゴリズムが可能です」と理解しています。私はそれを明確にしないことをお詫びします。私は、コンピュータの言語を分類することに本質的なものがあるのか​​、それとも人々がその上に構築する戦略なのかを尋ねています。私はそれが後者だと思うし、あなたたちはそれを確認した。言語が何かを分類しているかどうかはわかりませんが、パフォーマンスの違いを認識しています。

Answer 1

ここにキーがあります。 の言語は、データ構造がソートされているのかソートされていないのかを知ることはできません。実際には、それが実際にどのようなデータ構造になっているかは気にしません。

これを考慮してください：挿入や削除は実際には何を意味していますか？新しいアイテムを挿入したり既存のアイテムを削除するためには、正確な手順を実行する必要があります。これらの操作の正確な意味は、使用しているデータ構造によって異なります。配列はリンクされたリストとは非常に異なった新しい要素を挿入します。

したがって、これらの操作は、これらの操作が適用されているデータ構造のコンテキストで定義されている必要があります。 の言語は、一般に、これらのデータ構造を扱うキーワードを提供していません。付属のライブラリには、これらの操作を実行するメソッドを含むこれらの構造の組み込みの実装が用意されています。

元の質問：リストがソートされているかどうかを言語がどのように知っていますか？ソートされたリストを扱う方が効率的な理由は何ですか？答えは、私が上で述べたことから明らかなように、言語はリストの内部について知っているわけでもなく、知るべきでもない。ソートされているかどうかを知っている、使用しているリスト構造の実装と、新しいノードを順序付けられた方法で挿入する方法です。たとえば、特定のデータ構造では、特定の文字で始まる単語の位置を特定するために索引（本の索引によく似ています）を使用することができます。したがって、ソートされていないリストが全体を通過する時間が短縮されますリスト、一度に1つの要素。

これは少し明確になります。

Answer 2

リストは

をソートする際の言語を使用すると、言語インタプリタを意味するかを知ることができますか？もちろんリストがソートされているかどうかをチェックするだけで、各要素が前のものよりも「大きい」かどうかをチェックするだけです。私は通訳がこれをしているのか疑問です。なぜリストがソートされているかどうか、彼らは気にする必要がありますか？

一般に、「Cinammon」をリストに挿入する場合は、挿入先を指定するか、末尾に追加するだけです。リストがあらかじめソートされているかどうかは、通訳者にとって重要ではありません。ソートされたリストがソートされたままであるかどうか、ソートされる必要があるかどうかを決定するリストを使用する方法です。 （たとえば、バイナリ検索を使用してリスト内の何かを検索しようとすると、リストをソートする必要がありますが、の場合はでなければなりません）。 （？）で私が使用している言語私の知る限り

...

...は、リストがソートされているかを知りません。単なるリストです。また、「ワイドスクリーン」の視野を持たないため、Aチャンクがどこで終了し、Cチャンクがリストの外側から始まるかはわかりません。そこで、各配列文字列の最初の文字と挿入文字列の最初の文字を比較します。挿入文字が大きい場合は、次の文字列に移動します。文字が一致すると、次の文字に移動します。次の文字列に移動し、配列のcharが挿入のcharより大きい場合、charがそこに挿入されます。

あなたが言っていることは、挿入されているものより「大きい」最初の要素を探して、その直前に新しい要素を挿入することです。これは、既にソートされている場合、リストの「ソート」プロパティを維持することを意味します。これは、ソートされていないリストの場合、ひどく非効率的です。また、挿入ポイント（線形検索）を見つけるために説明する手法は、実際に何が起こっているのかは非効率的です。私はリスト/言語の意味論についてのあなたの理解が正しいとは思わないでしょう。

特定の言語で具体的な例を挙げておけば、多くの役に立ちます。

Answer 3

言語はそのようなことを知らない。

一部のプログラミング言語には、データ構造を含む標準ライブラリが付属していますが、そうでない場合は、通常、ライブラリにリンクできます。

これらのデータ構造の一部は、順序を維持するコレクション型です。

ので、ご注文のコレクション型を表すデータ構造を持って与えられ、それはアイテムが追加または削除されるたびに、コレクションの順序を維持するそのデータ構造です。

最も基本的なコレクションタイプ、つまり配列を使用している場合は、言語、ランタイム、データ構造自体（配列）のどちらも、アイテムを挿入するポイントが少しでも気になりません。