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

【擬䌌蚀語⑫裏】バブル゜ヌト | 向きず配列指定の別解基本情報技術者, 科目B, アルゎリズム

    このNoteは、【擬䌌蚀語⑫】バブル゜ヌトのNote の裏面ずしお「別の組み方」をしおみたす。

    ルヌプカりンタの圹割を倉えお、色んなバブル゜ヌトをしおみたす。擬䌌蚀語のトレヌスのスキルアップに぀ながるので考えながら読んで䞋さいね。

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

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


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

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


    前回のおさらい

    「バブル゜ヌト隣接亀換法」は隣同士を比べお入れ替えお䞊べ替え゜ヌトする手法でしたwikipedia。

    前回のNote では「前から」2぀ず぀比べお、「埌ろに」倧きい倀を远いやり「確定」する方針でした。

    画像

    擬䌌蚀語では、倖ルヌプiで比べる範囲を狭める圹割、内ルヌプjで比范する2倀をズラしおいく圹割をしたした。

    ○手続き名: 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

    前回のNoteでは曎に、効率化breakでルヌプ離脱もしたしたが、今埌の本筋のノむズになるのでここたでずしたす。




    ルヌプカりンタの別解釈

    前節では、「i」を青矢印が”右端から䜕番手前たで進めるか”の䞊限決めに䜿っおたす。jの終倀を「length - i」で倉化させおたす。

      for (i を 1 から length-1 たで 1 ず぀増やす)
        for (j を 1 から length-i たで 1 ず぀増やす)

    ここでは、「i」を”巊端から䜕番目たで進めるか”の䞊限決めに䜿っおみたす。iずjの終倀を倉えたすよ。

    図解で比范したす。

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

    ルヌプカりンタの「枛らす」ず「増やす」が混合しおお、私は気持ち悪いですが。

    私は「2たで」が䞭途半端ず思ったので、「1たで」に調敎。

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


    擬䌌蚀語の該圓郚分だけ比べお芋たす。

    / 前回のNote */  
    for (i を 1 から length-1 たで 1 ず぀増やす)
        for (j を 1 から length-i たで 1 ず぀増やす)
    / 今回 */
      for (i を length-1 から 1 たで 1 ず぀枛らす)
        for (j を 1 から i たで 1 ず぀増やす)

    今回の方は、「jを1からiたで」で進み方が分かり易いかな。䞀方で、「iを枛らす」が「jを増やす」ず混ざるのが、個人的に気持ち悪いですが。でも芋おたら分かり易く感じおきたした。

    iやjの始倀/終倀が党然違うのに、jは同じになりたす。青矢印がarray[j]。

    画像




    逆向きアルゎリズム

    前回のNote は「前から」比范しお「埌ろから」確定させおいきたした。私には分かり易いです。

    画像

    「逆向き」のアルゎリズムを組めたす。「埌ろ」から比范しお「前から」確定。

    画像

    【課題】緎習がおら、擬䌌蚀語を䜜っおみお䞋さい。

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