プログラミング入門

こんにちは、Torusです。

今回の目標

以下の知識が得られることを目標とします！

• 挿入ソートとはどのようなアルゴリズムであるか？
• 実行手順
• C言語における記述

挿入ソートとはどのようなアルゴリズムであるか？

まずは抽象的に説明しますが、後でちゃんと一つ一つ説明するので安心して下さい。

挿入ソートとは、配列の要素を一つずつ取り出し、既にソートされた部分に適切に挿入していくことで、配列全体を昇順もしくは降順に並び替えるアルゴリズムです。

上記の文章だけ見て、「フムフムなるほどな!」となる人はそうそういないのではないでしょうか？
順を追って説明していきます。例として、下記の数の入ったブロックの図のようなものをソートしたいとします。

今は「3, 1, 4, 2」と並んでいる訳ですが、最終的には、「1, 2, 3, 4」という風に並び替えたい訳です。
これを昇順にソートすると言います。左から右へ昇っていくイメージです。
逆に、「4, 3, 2, 1」という風に並び替えることを降順にソートすると言います。これも同様に、
左から右へ降りていくイメージです。

実際の実行手順

それでは、まず実行手順の大枠をお話します。より詳細な話は後でするので、無理に理解しようとせずに気楽に見て下さい。
注意事項として一番左のブロックは0番目のブロックとし、最後のブロックをn番目のブロックとします。また、議論を簡単にするため、ソートするブロックは全て異なる数のブロックであることとします。

A. 　基準値を0~n番目まで順次変更して以降の処理を繰り返し、n番目までの比較が終わったらアルゴリズムを終了する。

1. 0番目からi-1番目までが整列済みブロックであるならば、基準値をi番目とする。

B. 　基準値の値が定まり処理が終了するまで2の処理を繰り返し行う。

2. i番目の基準値と整列済みブロックとで大小比較を行う。このとき、大小比較について、i-1, i-2, i-3, …, 0の順で基準値と比較を行う。大小比較の結果によって、以下のような処理を実行していく。

2.1 (基準値より小さい値がない場合) 基準値とソート済みブロック全てを比較した結果、ソート済みブロックの中に基準値より小さい値がなかったときは基準値のブロックを先頭に入れて、B.の処理を終了し、Aに戻る。
2.2 (基準値の方が値が小さい場合) 基準値とk番目のブロックを比較した結果、基準値の方が値が小さいならばk+1番目ブロックの値をk番目のブロックの値にする。ただし、k=0のときは2.1の処理を行う。
2.3 (基準値の方が値が大きい場合) 基準値とk番目のブロックを比較した結果、基準値の方が値が大きいならばk+1番目ブロックの値を基準値のブロックの値にし、B.の処理を終了し、Aに戻る。

Aの処理について

まず、基準値の説明をします。唐突ですが皆さんに質問です。下記の図を見て下さい。

左側のオレンジのブロック1, 4は昇順に整列済みとします。このとき、青のブロック2をどこに差し込めば良いでしょうか？もちろん、1と4の間ですよね。この例のようにどこに差し込むかを決めようとしているブロックを基準値と言います。実際の処理では、この基準値を一番左のブロックから一番右のブロックに順次変更していきます。

Bの処理について

Bの処理は具体的に基準値をどこに差し込むかを決定する処理です。その処理が2.1~2.3の3パターンに分かれているだけです。それでは一つずつ見ていきましょう。

2.1 (基準値より小さい値がない場合)の処理について

下記の図を見て下さい。

左側のオレンジのブロック3, 7は昇順に整列済みとします。このとき、基準値である青のブロック1をどこに差し込めば良いでしょうか？答えは、先頭ですよね。この理由を言語化すると、整列済みのブロックと基準値となるブロックの中で一番値の小さいブロックが基準値だからです。

2.2 (基準値の方が値が小さい場合)の処理について

次も先程と同じ例を使いますが、分かりやすさのため、あえてソートしたいブロック列の方では基準値1の部分もオレンジ色のブロックにして、青ブロックの基準値を別で用意します。

青ブロックと整列済みブロックである3, 7を比較します。より具体的には、整列済みブロックの一番右側である7から比較します。基準値1と7を比較すると基準値1の方が小さいので、このときは、7を右側のブロックへコピーします。つまり、下記の図のようになります。

ここで皆さんの中で「なぜ上記のようなコピーをするのか」という疑問が生まれるかもしれません。このようなコピーをする理由として、気持ち的にはコピーではなくて下記の図のように右側に数をスライドさせたいという背景があります。

ただ、あえて真ん中のブロックのデータを消す手間を掛ける必要がないのでコピーします。

次に、基準値1と3を比較すると、基準値1の方が小さいので、3を右側のブロックへコピーします。つまり、下記の図のようになります。

先程と同様に気持ちとしては下記の図のようになります。

全て比較し終わって先頭まで来てしまったので、2.1の手順の通り、先頭に基準値を入れてBの処理は終了です。

2.3 (基準値の方が値が大きい場合)の処理について

左側のオレンジのブロック1, 4は昇順に整列済みとします。このとき、青のブロック2の差し込み手順を考えましょう。

まず、基準値2と4を比較すると、基準値2の方が小さいので、4を右側のブロックへコピーします。つまり、下記の図のようになります。

気持ちとしては下記の図のようになります。

次に、基準値2と1を比較すると、基準値2の方が大きいので、1の右側に基準値を入れてBの処理は終了です。

C言語における記述

main関数は書かないで、挿入ソートの関数部分だけ解説します。挿入ソート関数は以下のように記述出来ます。

void sort(int data[], int n){
   int i, j, base, num;
   for(i=1;i<n;i++){
      base=data[i];
      for(j=i-1;j>=0;j--){
         num=data[j];
         if(base<num) data[j+1]=num;
         else{
            data[j+1]=base;
            break;
         }
      }
      if(j==-1) data[0]=base;
   }
   return;
}

まず、関数sortの引数について説明します。data[]はソートするブロック達の中の数字、すなわち、ブロック達そのものを表す配列と言っても良いでしょう。nはデータ数、すなわち、ブロックの数です。また、このアルゴリズムで用いられている文字であるbaseは基準値であり、numは基準値と比較する数になります。

今まで学んできたものとコードを見比べて理解を深めて下さいね。
では、また！

Torusです。それでは、今日はまずC言語で画面に指定の文字を表示して見ましょう！

今回の目標

今回は下記のコードを理解することが目標です。

#include<studio.h>

int main(void){
    printf("Hello world!");
    return 0;
}

main関数について

それではまず、main関数について話をしていきたいと思います。ここで、main関数について専門的に長々と「intは~を意味してて」とか「関数とはそもそも~」とか話をしても良いのですが、いきなりそれをやると初学者は学ぶ気が失せてしまうと思います。なので、専門的なことは後々解説するとして、今回はmain関数、すなわち、下記の箇所

int main(void){

    return 0;
} 

#includeについて

これで今回のレクチャーは以上です‥と言いたいところですが、まだ解説しないで残っているものがありますね。そうです、「#include <stdio.h>」です。これは、プログラムで標準入出力関数を使うためのライブラリを読み込むために使用しています。うーん、急に難しくなったと感じたかもしれませんが、これから丁寧に説明していくので安心して下さいね。

まず、ライブラリについて説明します。唐突ですが、皆さんは自宅でおにぎりを作りたいとなったら、畑を買って米から作ろうとする人はいますでしょうか？(笑) おそらくそれは少数派なんじゃないかなと思います。多くの人は誰かが作った米をお店で買って、おにぎりを作るのではないでしょうか？それと同様にライブラリというのは米の例でいくと、お店のようなもので、誰かが作ってくれた関数が#include<stdio.h>を書くと使用出来るようになります。つまり、誰かが作ってくれた関数を使用して、プログラムを作成する作業をしようとするときに、#include<stdio.h>が必要になるわけですね。もうちょっと正確に言うと、今回は#include<stdio.h>の中にprintfが品揃えされているので、printfを使いたいならプログラムの最初に#include<stdio.h>を宣言しないといけない訳です。また、お店もお肉屋さんもあればお魚屋さんもある訳で、#include<stdio.h>以外にも#include<stdlib.h>とか他に様々なものがあります。今後色々と解説する中で#include<stdio.h>以外も紹介します。

それでは今回は以上となります、お疲れ様でした！良かったらコメントをして貰えると嬉しいです！

こんにちは、Torusです。

これからプログラムの基礎について、めちゃくちゃ噛み砕いた解説を投稿していきます。

これから情報系の道に進まれた方や大人になってからプログラミングを学びたいと思ったけど、独学では敷居が高いと感じる方にオススメです！

まず始めに解説するのはC言語です。実用上、Pythonの方が有益なんじゃないかなど様々な意見があるでしょう。しかし、私個人の意見としては、C言語は大抵の言語の基礎が詰まっているのです。言い換えれば、C言語が出来れば大抵の他の言語は余裕になります。逆に、Pythonから学んでしまうと、少なくともC言語よりは応用が効かない部分が出てくるでしょう。

詰まるところ、私のオススメはC言語をマスターしてしまうことで揺るぎないプログラミングの基礎力を身に付けることにあります。

ということで、私はこれからC言語の解説記事を投稿していくので、もし良かったら是非見にきて下さい！