マージ基準
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/18 08:12 UTC 版)
ティムソートは、安定ソートアルゴリズムであり（同じキーを持つ要素の順序が保持されます）、バランスの取れたマージ（マージにより、同様のサイズの並びがマージされます）の実行に努めます。 並べ替えの安定性を実現するために、連続する並びのみがマージされます。 2つの連続しない並びの間に、並び内に同じキーを持つ要素が存在する可能性があります。これらの2つの並びをマージすると、等しいキーの順序が変更されます。この状況の例（[]は順序付けられた並びです）：[1 2 2] 1 4 2 [0 1 2] バランスの取れたマージを追求するために、ティムソートは、スタックの最上位で3つの並び、 X 、 Y 、 Zを考慮し、不変条件を維持します。 |Z| > |Y| + |X| |Y| > |X| これらの不変条件のいずれかに違反した場合、 YはXまたはZの小さい方とマージされ、不変条件が再度チェックされます。不変条件が保持されると、データ内の新しい並びの検索を開始できます。 これらの不変条件は、バランスのためのマージの遅延、キャッシュメモリでの並びの新たな発生の活用、およびマージの決定を比較的簡単にすることの間の妥協点を維持しながら、マージをほぼバランスの取れたものとして維持します。
※この「マージ基準」の解説は、「ティムソート」の解説の一部です。
「マージ基準」を含む「ティムソート」の記事については、「ティムソート」の概要を参照ください。
ウィキペディア小見出し辞書の「マージ基準」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- マージ基準のページへのリンク
