メインコンテンツへスキップ
見出し画像

整列済みデータの併合とマージソート

    用語の意味


    併合は、二つの整列済みの列を一つの整列済みの列にまとめる処理です。マージソートでは列を分割し、それぞれ整列してから併合します。


    解き方と例


    昇順なら左右の未処理部分の先頭を比較し、小さい方だけを出力してその側を一つ進めます。片方が空になれば残りを続けて出力できます。各要素を一度ずつ出力するため、併合にかかる処理量は要素数の合計に比例します。


    確認問題【オリジナル】


    [2, 6, 9]と[1, 4, 8]を併合するとき、先頭3件と、その直後に比較する2値は何ですか。


    答えと解説


    出力は1、2、4です。左は6、右は8が未処理部分の先頭になるため、次は6と8を比較します。


    IPA 基本情報技術者試験シラバス

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ