4

そのため、プロジェクトでは、部品の1つをソートする必要があります。これはすべて MIPS アセンブリ言語で行われます。現在、挿入またはバブルソートのどちらを使用するかについて議論しています。これら 2 つは Merge や Quick sort に比べて遅いことはわかっていますが、これを取得しようとしているのは静的/動的命令の最小数です。この場合、どちらがより効率的でしょうか? 速度とメモリ使用量の間には常にトレードオフがあるように感じます。本当?

4

2 に答える 2

2

ソートする配列のサイズに大きく依存します。大きな配列の場合、バブル ソートは非常に遅くなる傾向があるため、単純なソート アルゴリズムを使用します。

ほとんどの人は、コード サイズが小さいため、配列が十分に小さい場合、バブル ソートがクイック ソート (およびその他の "高速" ソート) よりもさらに高速になることを知りません。

そう:

  1. 配列が可変サイズで、最大サイズがかなり大きい場合 - クイックソート (または同様のもの) を使用するか、後でアセンブリプログラムがいかに遅いかを説明する必要があります。:)

  2. 配列が十分に小さい場合 (おそらく数百要素まで)、バブル ソートを使用すると、小さなコード サイズと高いパフォーマンスの両方が得られます。

  3. 私の経験では、配列の並べ替えはそれほど一般的な操作ではありません。これらの配列を並べ替える必要があると本当に本当に確信していますか?

于 2013-07-07T09:36:24.540 に答える
0

挿入ソートについての私の記憶では、一度に 1 つずつ新しいレコードを受け取るので、ソートするデータが既にある場合は、2 倍のサイズのデータ​​が必要になります。1 つは読み取り用、もう 1 つは書き込み用です。重要なデータセットの場合、これはおそらく並べ替えアルゴリズムよりも多くのメモリを消費します。バブル ソートはその場で実行できます (つまり、ソートするデータのブロックが既にある場合、データに応じて、1 つのレコードまたは 1 バイトを格納するのに十分な追加のメモリのみが必要です。

バブル ソートは、記述するコードも少なくて済みます。

速度とメモリ (または、実際には任意の 2 つのリソース) の間には常にトレードオフが存在しますが、常にそうであるとは限りません。ただし、メソッド A がメソッド B よりも高速で単純であり、メモリの使用量が少ない場合、B が実際に競合することはありません。

于 2013-07-06T02:59:09.007 に答える