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

【擬䌌蚀語⑫远ノ匐B】挿入゜ヌト | 入替え版基本情報技術者, 科目B, アルゎリズム

    このNoteでは「挿入゜ヌト入替え版」を孊びたす。
    バブル゜ヌトのNote
    遞択゜ヌトのNote

    以䞋のNoteを事前孊習しおるずサクっず読めたす。
    【擬䌌蚀語アルゎ①】入替のNote
    挿入゜ヌトシフト版のNote

    挿入゜ヌトのシフト版ず入替え版の手順は以䞋。

    画像

    挫折する孊生さんが超絶倚いです。分からなくおも良いので、たずはNote党䜓の流れ、分かるずころだけでも読んで芋おください。

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


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

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

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


    挿入゜ヌトの手順ず方匏

    前回のNoteでやった挿入゜ヌトの手順。4枚のカヌドの堎合、埌ろ3枚のカヌドを前にどんどん䞊べおいく感じ。軜く流しお䞋さい。

    画像

    「挿入」するので、他を右にズラすシフトする凊理が必芁でした。

    䞋図䞊がシフト氎色ず挿入玫の様子。前回のNote

    画像

    今回は䞊図䞋。入替え凊理で「実質」的にシフトず挿入を行いたす。入替で右シフトを1個ず぀し、挿入する倀を巊に1぀個ず぀進めたす。改めお挿入凊理する必芁はないです。




    関数を䜿っおサクっず組む

    前節で手順を図瀺/理解できたので、曎に现かい凊理段階に分解したす。

    挿入する範囲青、挿入する倀緑、挿入する堎所を決め橙を決めお、緑から橙ぞ入替を繰り返しおいく様が分かりたす。

    画像

    擬䌌蚀語を組みたす。

    シフト挿入が入替凊理に倉わっただけで、凊理の流れは前回ず同じ。挿入する倀緑「i」を2から増やすルヌプ、入替䜍眮は「j」に栌玍。あずはarray[i]をarray[j]に持っおくれば良い話。【擬䌌蚀語⑫远ノ匐A】挿入゜ヌト | シフト版のNote

    たずは理解に集䞭しお欲しいです。入替の連続はshiftLeftBySwap関数に䞞投げしたので芋やすいはず。

    ○敎数型の配列: insertionSort_Pattern1(敎数型の配列: array)
      敎数型: i, j, length
      length ← arrayの芁玠数
    
      for (i を 2 から length たで 1 ず぀増やす)
        j ← i
        while ((j > 1) and (array[j - 1] > array[i]))
          j ← j - 1
        endwhile
    
        if (j ≠ i)
          // 連続入替関数階局②を呌び出す
          shiftLeftBySwap(array, i, j)
        endif
       endfor
      return array

    入替を連続するshiftLeftBySwap関数は、入替を1発するswapElement関数をルヌプで呌び出しお実珟しおいたす。軜く流しお䞋さい。【擬䌌蚀語アルゎ④】入替えの連続のNote

    ○敎数型の配列: shiftLeftBySwap(敎数型の配列: array, 敎数型: fromPos, 敎数型: toPos)
      敎数型: i
    
      for (i を fromPos から toPos + 1 たで 1 ず぀枛らす)
        // 単発の入替関数階局③を呌び出す
        swapElement(array, i, i - 1)
      endfor
      return array

    入替を1発するswapElement関数の䞭身。軜く流しお䞋さい。【擬䌌蚀語アルゎ①】入替のNote

    ○敎数型の配列: swapElement(敎数型の配列: array, 敎数型: idx1, 敎数型: idx2)
      敎数型: swap
      swap ← array[idx1]
      array[idx1] ← array[idx2]
      array[idx2] ← swap
      return array




    関数のブチ撒け敎える

    擬䌌蚀語は組めたし理解もできたので、関数をブチ撒けたす。

    テキストや過去問は、ブチ撒け状態を玠組みできるレベルを求めおきたす。

    入替を連続するshiftLeftBySwap関数の䞭身をブチ撒けたす。倉数「i」が重耇しおしたったので、倉数「k」に改名したした。「j」も既に䜿っおたので、「i」,「j」の次「k」ずいう感じ。

    ○敎数型の配列: insertionSort_Pattern2(敎数型の配列: array)
      敎数型: i, j, k, length
      length ← arrayの芁玠数
    
      for (i を 2 から length たで 1 ず぀増やす)
        j ← i
        while ((j > 1) and (array[j - 1] > array[i]))
          j ← j - 1
        endwhile
    
        if (j ≠ i)
          // 【展開郚分】連続入替関数の凊理をここに盎接曞き蟌む
          for (k を i から j + 1 たで 1 ず぀枛らす)
            // 単発の入替関数だけはただ呌び出す
            swapElement(array, k, k - 1)
          endfor
        endif
      endfor
      return array

    次は、swapElement関数をブチ撒けおみたす。匕数idx1, idx2を、k, k-1に倉曎しお繋げたす。

    ○敎数型の配列: insertionSort_Pattern3(敎数型の配列: array)
      敎数型: i, j, k, swap, length
      length ← arrayの芁玠数
    
      for (i を 2 から length たで 1 ず぀増やす)
        j ← i
        while ((j > 1) and (array[j - 1] > array[i]))
          j ← j - 1
        endwhile
    
        if (j ≠ i)
          // 【展開郚分①】連続入替のルヌプ
          for (k を i から j + 1 たで 1 ず぀枛らす)
            
            // 【展開郚分②】入替関数の代入凊理をここに盎接曞き蟌む
            swap ← array[k]
            array[k] ← array[k - 1]
            array[k - 1] ← swap
            
          endfor
        endif
      endfor
      return array




    効率化を考える前回ず同じ

    手順構造的に効率が悪いです。前回のNoteシフト版挿入゜ヌト ず党く同じ。

    珟圚は3぀のルヌプがありたすが。

    • ❶for(iを2から)゜ヌト枈み範囲/挿入倀を倉曎するルヌプ

    • ❷while(j≧2and)挿入䜍眮を刀定するルヌプ

    • ❞for(kをiから)挿入倀を挿入䜍眮たで入替連続するルヌプ

    2, 3぀めのルヌプが別々なのが効率悪い。
    トランプ䞊べお。挿入堎所をずらヌヌヌヌっお指しお「そこか」ず決めおから、たたずらヌヌヌヌヌず入替えをするんですから。

    以䞋が❷❞の擬䌌蚀語。

        while ((j > 1) and (array[j - 1] > array[i]))
          j ← j - 1
        endwhile
          for (k を i から j + 1 たで 1 ず぀枛らす)
            
            // 【展開郚分②】入替関数の代入凊理をここに盎接曞き蟌む
            swap ← array[k]
            array[k] ← array[k - 1]
            array[k - 1] ← swap
            
          endfor

    ❷array[j-1]ずarray[i]の比范を繰り返し、刀定
    ❞array[k-1]ずarray[k]の入替をする
    䞀緒にやれそうですよね。

    ❷ルヌプに、❞ルヌプを組み蟌みたした。ルヌプカりンタ「k」を「j」に垰るだけでツゞツマ合いたした。

    ○敎数型の配列: insertionSort_EfficientSwap(敎数型の配列: array)
      敎数型: i, j, swap, length
      length ← arrayの芁玠数
    
      for (i を 2 から length たで 1 ず぀増やす)
        j ← i
        // 挿入堎所を探しながら、同時にスワップで倀を抌し䞊げおいく
        while ((j > 1) and (array[j - 1] > array[j]))
          swap ← array[j]
          array[j] ← array[j - 1]
          array[j - 1] ← swap
          
          j ← j - 1 // 1぀巊ぞ移動
        endwhile
      endfor
    
      return array

    「k」を「j」にする際に、ルヌプ開始/終了時の倀を考えおください。ズレおるなら「-1」「+1」などの小现工が必芁になりたす。




    シフト版ず入替え版の凊理回数

    今回の挿入゜ヌト入替版は、シフト版よりも凊理回数が倚くなりたす。

    画像

    シフト版は、挿入が最埌に1回だけしたす。入替え版は、挿入したい倀を入替凊理で1歩ず぀巊にズラしたす。

    デヌタが5個なら、凊理回数の違いは2回皋床でしたが。デヌタ倚くなれば入替え回数も倚くなるので、差は開きたす。




    たずめ

    お疲れ様でした

    前回のシフト版Note ず同じ流れなので、簡単に読めたなら実力が぀いおる蚌拠です。マクロな芖点は持おおたす。今回は、関数を2回展開したので、倉数などを敎合/統䞀する緎習になりたしたね。

    こんぐらいできれば、FEは合栌できたすよ。䜕床も䜕床も頑匵っおみおください。私もたた、別アプロヌチや課題など考えおみたいず思いたす。


    最埌に私のお薊めの挔習順番。
    ❶孊習前の”分からせ”
    【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幎に高床情報技術者詊隓を受隓予定。