どのソート方法が並列処理に最適ですか？

私は今私の古い学校の課題を見ていて、質問の解決策を見つけたいと思っています。どのソート方法が並列処理に最適ですか？

どのソート方法が並列処理に最適ですか？クイックソート

ソート選択ソート

をマージ

バブルソート
私はクイックソートを推測する（またはソートマージ？）答えです。

正しいですか？私は、ソート

あなたがデータセットを分割し、それらの上に並列処理を行うことができますマージ考える

2009-11-23 Billy

などがマージソート、クイックソートも簡単に、その分割統治性質のために並列化することができます。個々のインプレースパーティション操作は並列化が難しいですが、一度分割されると、リストの異なるセクションを並行して並べ替えることができます。

他のパラレルソートアルゴリズムよりもパラレルクイックソートの利点の1つは、同期が必要ないということです。新しいスレッドは、サブリストが機能するようになるとすぐに開始され、他のスレッドとは通信しません。すべてのスレッドが完了すると、ソートが完了します。

http://en.wikipedia.org/wiki/Quicksort

出典

2009-11-23 16:08:51

+1：Quicksortは、一度分割すると同期する必要はありません。 Mergesortは、同期をマージする必要があります。 –

"他のパラレルソートアルゴリズムよりもパラレルクイックソートの利点の1つは、同期が必要ないということです。" Err、no。答えを返す前にサブタスクが完了するのを待つ必要があります。これは同期化です。 –

出典

2009-11-23 15:55:11 ufukgun

+1。 – Will

私の名前はUfukGünですが、英語では面白そうです:) – ufukgun

Mergesortはソート結果をマージするためにスレッド間の同期が必要です。 Quicksortはスレッド同期を必要としません。 –

これは、並列化の方法に完全に依存します。マルチスレッドの一般的なコンピューティングの場合、マージソートはかなり信頼できるロードバランシングとメモリローカリゼーションのプロパティを提供します。ハードウェアで大きいsorting networkの場合、Batcher、Bitonic、またはShellソートの形式は、良いO（log²n）パフォーマンスが必要な場合は実際に最も適しています。

出典

2009-11-23 16:14:41

ここで唯一の正解であるため+1。 –

私はマージソートがここで最高の答えだろうと思います。マージソートの背後にある基本的な考え方は、問題を個々のソリューションに分割することです。それらをまとめてマージします。

私たちが実際に並列処理で行っていることはそうです。問題全体を小単位ステートメントに分割して並列に計算し、結果を結合します。ありがとう

出典

2012-03-26 19:21:12 mojito89

並べ替えが2つのサブ配列で行われ、最後に比較および並べ替えが行われるため、マージソートです。あなたのニックが私を怖がらせるにもかかわらず、これらは並行して行うことができます

出典

2012-09-06 03:51:46 Nimmy

既存の回答を複製する必要はないと思います。 – Mysticial

どのソート方法が並列処理に最適ですか？

答えて

関連する問題