乱れた観察記録の山を正しく、問題なく整理するにはどうすればよいでしょうか?
まずどのレコードが古いかを比較し、次にレコード全体を移動して、データがどのように配置されているかを自分の目で確認してください。
写真を何枚も撮った後、記録カードがスクランブルされてしまいました。各カードには番号と識別文字が付いています。小さいものから大きいものまで並べ替える場合、同じ番号のカードが 2 枚失われることはありません。
まずは推測してください
両方の観測レコードのソート値は 2 です。ソート時にどちらかを削除する必要がありますか?
答えと解説を見る
いいえ、両方の記録を保持する必要があります。 — 値が同じであっても、レコードが同じであるとは限りません。ソートは順序を変更するだけであり、重複排除は行いません。
そして経験と科学を結びつける
まずは記録を広げてみましょう
各カードの文字は ID を記録し、番号は分類の基礎となります。同じ番号が複数回出現する可能性があり、レコードを破棄することはできません。
入力は、単なる異なる数値ではなく、一連のレコードです。
一度に 1 つの特定のアクションのみを実行する
移動の進行状況、比較または交換されたカードはオレンジ色で強調表示されます。プログラムは比較フェーズ中に値のみを確認し、交換フェーズ中に完全なレコードを移動します。
比較→交換するか決める
アプローチを変えても結果は同じ
オリジナルの本では、ペアごとの交換、最初に最小のものを見つける、およびパーティションの迅速なソートを提供します。異なるステップで同じ昇順の値を取得できますが、同じ値を持つレコードが元の順序を維持しない可能性があります。
SIMPLE / BETTER / QUICKSORT
データが増加するにつれて、ステップ数の重要性が増します
最初の 2 つの方法の比較の数は N² に応じて増加します。クイック ソートは通常、約 N log N ですが、すべての入力に対して最速であることが保証されません。この例では、カウントは実際の測定値であり、マシンが実行されている秒数ではありません。
比較、交換の回数、実際の消費時間を区別する必要があります。
計算の流れを詳しく見る
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条記録的身份与内容保持完整
これはアルゴリズム規則のクラスであり、代入によって得られる天文学的な公式はありません。比較によって順序が決まり、交換ではレコード全体を移動する必要があります。同じキー値であっても、レコードを破棄できるわけではありません。
試してみてください
同じカードのセットを使用して 3 つの方法を比較します。進行状況を 100% までドラッグし、数値が昇順になっていること、および A ～ H レコードがまだ存在していることを確認します。
見てみてください →
記号を覚える必要はありません
- N
- レコード数、このレッスンの画面は 8 です
- 比較する
- 2 つの値の順序を表示します。クイックソートはベースライン値とも比較します
- 交換
- 2 つの完全なレコードを交換する
- 基本値
- クイックソートは両側の値を分割するために使用されます
- 安定性
- 同じソート値を持つレコードが元の相対順序を維持するかどうか
アルゴリズム、精度、適用範囲
原書、第 6 章、印刷ページ 55 ～ 58、表 6.A。 3 つのアルゴリズムが実装されています。SIMPLE SORT は、前後の位置に従ってペアごとに比較および交換します。BETTER は、最初に残りの最小値を見つけてから交換します。QUICKSORT は、ダブル ポインター分割と中間要素の値に基づく明示的なスタックを使用します。このレッスンでは、間隔の長さに応じてスタック順序を最適化する元の BASIC の詳細を省略し、分割結果と実際の比較/交換トレースを保持します。クイック ソートの最悪のケースが N log N であるとは主張していません。デモンストレーション カード番号には実際の日付単位はなく、文字は ID を示すだけです。進捗率はアルゴリズムの個別のステップにマッピングされ、実際のステップ番号を示します。比較と交換は、実行秒数を除き、個別にカウントされます。同じ値を持つレコードの順序が安定しているという保証はありません。この章の最後にある文字列 ASCII ソートの概要がテキストで説明されており、対話では数値ソートのみが実装されます。ローカル AA+ はソート用の特別なモジュールを見つけられず、結果は独立したネイティブ数値ソートとステップごとの順列不変条件を使用して検証されました。
私の理解度チェック
2 つのレコードを比較する場合、データをすぐに交換する必要がありますか?
不確かな — 比較と交換は別のアクションであり、アルゴリズムの条件が満たされた場合にのみ交換されます。
ソート後の数値が同じということは、同じ値を持つレコードの順序も同じでなければならないということでしょうか？
不確かな — 同じ値を持つレコードの順序関係を保持するかどうかは安定性に関係します。このレッスンの 3 つの実装では、安定した並べ替えが保証されません。
元のコンピュータで測定された秒数を、今日の Web ページにかかった時間として直接使用できますか?
できない — ハードウェア、言語、実装はさまざまです。このレッスンでは、古いマシンを再利用せずに、再現可能な操作の数と秒数を比較します。
並べ替えでは、まずレコードが完全で正しい順序であることを確認し、次に運用コストを比較します。同じ値を持つレコードを重複ゴミとして破棄することはできません。
Jean Meeus · Astronomical Algorithms, 2nd ed. · いいえ。 6 章