0

挿入ソートは、ここに示す例のように、順序付けされていない配列でも機能します。タイトル（またはここ）のこのステートメントには、奇妙な理由で、挿入ソートの優先度キューを実装するための順序付き配列が必要ですが、なぜそのような要件があるのですか？このウィキペディア-ここにあるものは実際にはどういう意味ですか（下のスクリーンショット）？

ここに画像の説明を入力してください

4

1 に答える 1

4

この記事は、ソートのためのプライオリティ キューの使用法と、プライオリティ キューのさまざまな実装が使い慣れたソート アルゴリズムにどのように対応するかについて説明しています。

pop()比較関数によって定義された「最小」の要素を取り出し、push()新しい要素を優先度キューに入れる操作を持つ ADT 優先度キューを考えてみましょう。次にpush()、ソートされていない配列内のすべての要素をプライオリティ キューにプッシュしpop()、プライオリティ キューが空になるまでコールして、ポップアウトされた要素を配列に入れることで、ソートを実行できます (まあ、empty()ADT が有効かどうかを確認するメソッドを定義できます)。空の）。

疑似コード:

unsorted[]
sorted[]
priority_queue q

foreach element in unsorted
    q.push(element)

i = 0
while !q.empty()
    sorted[i] = q.pop()
    i = i + 1

次に、プライオリティ キューの実装方法について説明します。通常、ヒープで効率的に実装されます。ただし、ヒープである必要はありません。ウィキペディアの記事で説明されているように、順序付けされていない配列または順序付けられた配列を使用して、効率の低い方法で実装できます。push()実装がandpop()操作の要件を満たしている限り、問題ありません。

順序付けされていない配列の場合push()、最後の要素の直後に要素を配置することができます - それはunorderedであるためです。配列は順序付けされてpop()いないため、配列全体を検索して最大の要素を選択する必要があります。(順序付けされていない配列の最後の要素を、ポップアウトされる要素の位置にスワップすることで、簡単に削除できます)。これは、基本的にソートされていない要素 (優先キューにある) のリストを調べて、ソートされた部分に入れる最大の要素を選択するため、選択ソートに似ています。

ここの操作では、挿入ソートでの挿入操作が行われていることがわかりpush()ます。

順序付き配列の場合pop()、最初の要素を取り出すだけで済みます (削除は、開始インデックスを維持することで簡単に実行できます)。ただしpush()、順序を維持するために要素を配置する場所を見つける必要があります (順序付けられた配列であるため)。これは、現在の要素をソートされた部分 (順序付けられた配列として実装された優先キュー) に挿入しようとしているため、挿入ソートによく似ている部分です。

ここでの操作では、選択ソートでの選択操作が行われていることがわかりpop()ます。

于 2012-10-20T04:53:44.540 に答える