基数ソートに安定ソートアルゴリズムのみを使用する必要はありますか？

私は、基数ソートで不安定なソートアルゴリズム（クイックソートなど）を使用する際の危険性を理解しようとしています。また、どちらの場合でも安定したアルゴリズム（MSD基数ソートとLSD基数ソート）が必要ですか？基数ソートに安定ソートアルゴリズムのみを使用する必要はありますか？

ありがとうございます。

出典

2016-07-28 Sumukha Bharadwaj

※*は仕事をしますか？出力がソートされることを意味する場合は、MSD（安定/不安定）のRadixソートも同様に機能します。アルゴリズムが安定することを意味するならば、明らかに不安定なアルゴリズムが安定していないので、なぜ* any（安定/不安定）*が仕事をするのですか？あなたが話している*仕事*は何ですか？ – trincot

あなたのコメントを読んだ後、私は私の質問であいまいさを実感しました。また、私はRadixソートについての私の理解が完全に正しいとは思っていませんでした。私は説明を編集しました。 –

OK、*は安定したアルゴリズムであるとはどういう意味ですか*：この文脈では* must *という単語は理解できません。 – trincot

各パスの後に仮想ビンを連結することはできないため、MSD基数ソートは通常実用的ではありません。 8ビットバイトでソートすると、最初のパスの後に256個の別々のビンがあり、2回のパスの後、65536ビン、3回のパスの後、16777216ビン...。

LSD基数ソートは、仮想ビンが順番に連結されているため、より重要な「数字」を前のパスで確立された順序を保持する必要があるため安定している必要があります。 LSD基数ソートは、1900年代初期の古いカードソーターがどのように動作したかを示しています。

http://en.wikipedia.org/wiki/IBM_card_sorter#Earlier_sorters

出典

2016-07-28 06:17:03 rcgldr

基数ソートに安定ソートアルゴリズムのみを使用する必要はありますか？

答えて

関連する問題