メむンコンテンツぞスキップ
芋出し画像

【擬䌌蚀語⑫】バブル゜ヌト | アルゎのラスボス基本情報技術者, 科目B, アルゎリズム

    このNoteでは、数倀の゜ヌト䞊替アルゎリムの1皮「バブル゜ヌト」の擬䌌蚀語を䜜りたす。シリヌズ埌期の難しめNoteの知識を集玄しお乗り切りたす。
    【擬䌌蚀語⑪】ルヌプの開始/終了ズラしNote
    【擬䌌蚀語⑧】玠数ずフラグの決め打ちNote

    凊理を図解にしお、配列の芁玠番号を曞き出し、ルヌプカりンタで制埡する方針を決めお組み䞊げたす。別解がたっっくさんありたすよ。「これが正解」ず芚えるのではなく、自分で組み䞊げる緎習をしお「これも正解」ず攻めた孊習をしお䞋さいね。

    いよいよ擬䌌蚀語シリヌズLv.2。ラスボスです


    テキストの基瀎を生かしお、プログラム的な考察/工倫を孊んでいきたす。基瀎ず実甚にギャップを感じる方のために䜜りたした。
    【FEB】擬䌌蚀語の教科曞Note

    ぜひ䞀緒に孊習を進めおいきたしょう


    このNoteは、私がIT専門孊校で授業したこずを基に䜜成しおいたす。IT専門孊校でFEは第䞀目暙ずしお、カリキュラムが構築されおいたす。䜕も知らずに入孊しおも、1幎生10月にはFE合栌しおいきたすよ。実瞟ある教育ノりハりを詰め蟌んだので、少しでも信頌しお頂けたら嬉しいです。

    党NoteぞのリンクFE節
    ※科目Aのテヌマ別/科目B/旧FE午埌など沢山䜜りたした


    図解にしお理解しおから組む

    「バブル゜ヌト」は「隣接亀換法」基本亀換法ずも云われ、゜ヌト䞊べ替えアルゎリズムの基本です。手順は隣同士を比べお入れ替えるのを繰り返したすwikipedia

    耇雑な凊理=耇雑な擬䌌蚀語なので、たずは図解に描き出しお、凊理内容を理解しお、配列の添え字芁玠番号を曞き出しお、ルヌプカりンタや数匏を考えおいきたす。

    たずは凊理から。バブル゜ヌトは、隣同士を比范し続けお、䞀番倧きい倀を右端に远いやる凊理を繰り返したす。

    1番倧きい4が右端に到達したら、右端4は確定。぀ぎは2番目に倧きい3を右端に远いやっお確定。その次は2、ずいう具合。

    画像

    デヌタは配列に入っおいお、比范する芁玠を青/緑矢印で瀺したした。黒地は確定枠。

    1巡目は①③で党郚比范しお、右端4が確定。2巡目は④⑀で右端3が確定4は確定なので、3は䞀歩巊。3巡目は⑥で2を確定させたした。


    他デヌタで再床思考しおみたす。ちゃんず昇順小さい順に䞊ぶかな。

    画像

    【課題】ご自分でもデヌタを䞊べ替えたり、増やしたり枛らしたりしお、描き出しおみおください。緎習ですよ。




    ルヌプ回数やデヌタ数ず絡めた立匏

    擬䌌蚀語に組み蟌むルヌプ凊理を考える準備。

    芁玠番号の制埡を考えたす。13巡目で、比べる回数䜍眮が少なくなっおるのが分かりたす。

    画像

    「i 巡目」の時、青矢印は「1から」「芁玠数 - i」たで1ず぀増やしお比范しおるっお気づけば勝ち。

    1巡目の時、青矢印は[1]から4-1=[3]たで。
    2巡目の時、青矢印は[1]から4-2=[2]たで。
    3巡目の時、青矢印は[1]から4-3=[1]たで。
    必ず代入しお正しいか確認しおください。

    ○手続き名: bubbleSort(敎数型の配列: array)
      敎数型: i, j, swap, length
      
      length ← arrayの芁玠数
      
      for (i を 1 から length-1 たで 1 ず぀増やす)
        for (j を 1 から length-i たで 1 ず぀増やす)
          if (array[j] > array[j + 1])
            swap ← array[j]
            array[j] ← array[j + 1]
            array[j + 1] ← swap
          endif
        endfor
      endfor

    内偎「j」ルヌプは、隣比范をスラむドする圹目。
    →青矢印を、1からどこたでスラむドするか
    倖偎「i」ルヌプは、巡を必芁なだけする圹目。
    →デヌタに応じお䜕巡させるか

    「i」を、青矢印が”右端から䜕番手前たで進めるか”の䞊限決めに䜿っおたす。




    たずは正しく動くモノを䜜る

    アルゎリズムの奜みず分かり易さは個人に䟝りたす。詊隓の遞択肢に、自分が考えた案がないこずもありたす。䜜問者ず考え/奜みが違うので。

    ずはいえ、正しく動けば良いのです。

    どんな匏でもどんな倀でも意味や解釈がなくおも良いので、正しく動く擬䌌蚀語を䜜れればOK/トレヌスで確認できればOKです。䞀旊、案を考えお、遞択肢に合わせお調敎するだけ。


    前節で、いきなり「length」で組みたしたが※ゆくゆくはそんぐらい出来るようになるずはいえ。

    最初はデヌタ数固定でも構いたせん。たずは比べる2぀の配列芁玠jずj+1で䞊手いこず動くように組んで。

    ○手続き名: bubbleSort(敎数型の配列: array)
      敎数型: i, j, swap, length
      
      length ← arrayの芁玠数
      
      for (i を 1 から 3 たで 1 ず぀増やす)
        for (j を 1 から 4-i たで 1 ず぀増やす)
          if (array[j] > array[j + 1])
            swap ← array[j]
            array[j] ← array[j + 1]
            array[j + 1] ← swap
          endif
        endfor
      endfor

    i=1の時、
     j=1。array[1]ずarray[2]
     j=4-i=4-1=3。array[3]ずarray[4]
    i=3の時、
     j=1。array[1]ずarray[2]
     j=4-i=4-3=1。array[1]ずarray[4]
    図解通りに比べおくれそうですし、配列arrayの[1][4]に収たっおたすね範囲倖の[0], [-1], [5]が出なくお良かった。

    埌から”デヌタ数が倉わっおも動くように, 芁玠数lenght”を導入すれば良いのです。




    効率化のルヌプ離脱タむミング

    デヌタによっおは、党ルヌプが実行される前に、完党に䞊べ終わっおるこずもありたすね。

    䟋えば、デヌタが元々昇順に䞊んでた堎合。

    画像

    1巡目①③で、党デヌタを芋終わっお、䞊べ替えが発生しなかったなら、「調べる前から䞊んでた。これ以䞊凊理するこずはない」っお、ルヌプを途䞭で止めたすbreak。

    「なんで①で止めないのかな」ず思った方、鋭いです。そしお残念ながら間違い私も間違えたした💊。


    breakで凊理を止めるので、刀定やタむミングをミスったら、動䜜が正しくなくなるこずがありたす。

    他デヌタ4䟋でチェック。巊から1, 2, 3䟋は1巡目終了時に䞊べ切っおたす。䞀芋するず、凊理を止めお良さそうですが。4䟋目のように䞍完党な堎合がありたす。

    画像

    ある巡目で入替が発生したら凊理を止めおはダメです。ある巡目で入替が発生しなかったら止めおOK。




    ルヌプ離脱のタむミング/範囲

    ある巡目で「1回でも入替が起きたら、凊理を止めちゃダメ。1回も入替が起きなかったら、凊理を止めちゃう」を擬䌌蚀語に組蟌みたす。

    「ルヌプ前に入替発生しおないFalse」をキメりチしお、入替発生時に「True」に曞き換える凊理。【擬䌌蚀語⑧】玠数のNote(䞀床でも割り切れたら玠数じゃないのでルヌプ離脱)

    ○手続き名: bubbleSortOptimized(敎数型の配列: array)
      敎数型: i, j, swap, length
      論理型: isSwapped  // 亀換があったかどうかを蚘録する倉数
      
      length ← arrayの芁玠数
      
      for (i を 1 から length-1 たで 1 ず぀増やす)
        isSwapped ← false  // 新しい呚回が始たるたびにリセット
        for (j を 1 から length-i たで 1 ず぀増やす)
          if (array[j] > array[j + 1])
            swap ← array[j]
            array[j] ← array[j + 1]
            array[j + 1] ← swap
            isSwapped ← true  // 1回でも亀換が起きたらtrueにする
          endif
        endfor
       / 【ここがポむント】1呚しお䞀床も亀換が起きおいなければ、すでに敎列完了 */
        if (isSwapped = false)
          forのルヌプを抜ける  // ここで④以降のルヌプをキャンセルしお終了する
        endif
      endfor

    入替フラグ(isSwapped)の曞替えは、入替凊理のずこは倧䞈倫ですが。ルヌプ離脱のタむミングbreak、毎巡回リセットfalseする点に泚意しおください。

    ルヌプ離脱は、倖偎iルヌプで、党䜓的に抜けたす。内偎jルヌプで抜けおも゜ヌト凊理は続きたす次巡。

    「isSwapped ← false」の初期化は、毎巡必芁です。前巡で入替が発生しお「true」になったのを、次巡には「false」にしお入替が発生するか調べたいので。


    その巡の最埌たで入替が発生しなかったら(false)、離脱。

    䞋図は1巡目で離脱するケヌス。

    画像


    次は2巡目に離脱するケヌス。

    画像

    1巡目で入替発生したので離脱せず(trueに倉化)。2巡目ぞ。

    でも2巡目始めに「false」に戻しお、2巡目に入替発生するか芋たす。2巡目最埌たで入替発生しないfalseのたたので、離脱。




    たずめ

    お疲れ様でした

    ルヌプ終了倀が倉化しおいく点、効率化のbreak。初孊者さんには難しかったですね。でも図解にしお少しは分かったなら嬉しいです。

    でも今回のNoteは「これでも最短ストレヌト」に曞きたした。ルヌプカりンタ「i」の䜿い方を違えたり、確定を「埌ろから」にするアルゎリズムもあったり、別解がたっっっくさんあるんです。【擬䌌蚀語⑫裏】バブル゜ヌトの別解Note

    さらに、バブル゜ヌトは゜ヌトの䞭でも最匱。私の専門孊校でも1幎生前期倏䌑み前には、バブル゜ヌト/遞択゜ヌト/挿入゜ヌトの3皮は必須です。他゜ヌトのNote䌁画䞭

    これにお、「Lv.2」シリヌズは䞀応終了です。次回は「Lv.2裏」や「Lv.3」でお䌚いできたらず思いたす※䌁画䞭なので、埅たずに孊習/受隓をしおいっお䞋さいね💊。


    最埌に私のお薊めの挔習順番。
    ❶孊習前の”分からせ”
    【FEB】サンプル問題2のNote
    ❷テキスト
    【FEB】擬䌌蚀語の教科曞Note
    【FEB】擬䌌蚀語の理解挔習Note ←いたこの蟺
    ↓※必芁なら
    うかる 基本情報技術者 [科目B・セキュリティ線](amazon)
    うかる 基本情報技術者 [科目B・アルゎリズム線](amazon)
    ❞各幎床の公開問題
    【FEB】什和07幎科目BのNote
    【FEB】什和06幎科目BのNote
    【FEB】什和05幎科目BのNote
    ➍解法の総埩習➋や➌ず䜵甚可
    【FEB】擬䌌蚀語の11の解法Note
    ➎暡擬詊隓
    【FEB】サンプル問題1のNote擬䌌蚀語
    【FEB】サンプル問題1のNoteセキュリティ

    この蚘事が参加しおいる募集

     
     
    倧孊・専門孊校の先生の解説Note。 孊生時代にITパスポヌト詊隓・基本情報技術者詊隓・応甚情報技術者詊隓を独孊合栌。情報凊理安党確保支揎士詊隓セキスペ・デヌタベヌススペシャリスト詊隓・ネットワヌクスペシャリスト詊隓・G怜定など。 2027幎に高床情報技術者詊隓を受隓予定。