c - ソートが速い/簡単なのはどれですか? 配列か連結リストか?

Question

配列またはリンク リストを使用してデータを格納する必要があるプロジェクトをコーディングしています。後で、データをソートする必要があります。単純に交換するだけなので、配列をコーディングする方がソートしやすいと思います。リンクされたリストの場合、ポインターについて心配する必要があり (およびコードを記述する必要があります)、各要素へのアクセスは配列よりもコストがかかります。私は正しいですか？

Answer 1

ソートアルゴリズムとソート対象に大きく依存します。リンクされたリストをトラバースするコストは、配列内の要素にインデックスを付けるよりも確実に高くなります。ただし、並べ替えアルゴリズムに要素のシフトが含まれる場合、これはリンクされたリストでは一定の時間で実行できます (一方、配列では要素ごとに実行し、それぞれをコピーする必要があります)。リンクされたリストの要素の交換も一定時間です（ポインターを変更するだけです）が、配列では要素をコピーします（データによっては一定時間になる場合もあります）。

クイックソートを使用してソートしたい整数のセットについては、おそらく配列を使用する方が高速です。選択ソートを使用してソートする大きな構造のセットの場合、リンクされたリストの方が高速です。

次に、要素にどのようにアクセスするかという問題があります。並べ替えの意図が後で二分探索によって要素にアクセスすることであった場合は、間違いなく配列を使用することをお勧めします (二分探索は通常、連結リストの線形検索よりも遅いため、連結リストがバランスのとれた B- のようなものでない限り)。木）。

Answer 2

実装する並べ替えの種類によっては、コレクション内の要素へのランダム アクセスが必要になる可能性があります。それを念頭に置いて、配列は確かにより良い選択です。

先に進んで、これは学校/学習プロジェクトであると推測します (または、既存の並べ替え関数を使用しているはずですよね)。そのため、選択した並べ替えアルゴリズムは、この決定に影響を与えます。

通常、最速のソートはクイックソート (またはマージソート) であり、ランダム アクセス (したがって配列) の利点があります。スワップについてのあなたのアイデアも良いです。通常、その場でソートし、余分なメモリを割り当てないようにします。

Answer 3

必ずしもこの方法をお勧めするわけではありませんが (何をしているかによって異なります)、並べ替え基準がわかっている場合は、連結リスト ツリーを使用して並べ替えることができます。

数字だとしましょう:

struct treeNode {
  struct treeNode* greater;
  struct treeNode* lesser;
  int myValue;
};

おそらく、アルゴリズムを作成するのが最も難しいでしょう (特定の中間値が発生したときにノードをプッシュする必要があります)... 再帰関数とヘルパー関数をどれだけ使用したいかによって異なります。