パソコン日記

気づいたこと まとめてみる

C言語でバブルソートの実行時間を測る

ソートの実行時間を測る

以前の記事でプログラムの実行時間の測り方をご紹介いたしました。

1-compinfo.hatenablog.com

今回はバブルソートの実行時間を測定してみたいと思います。

バブルソートとは

バブルソート - Wikipedia

バブルソートwikipediaにあるように、ソートのアルゴリズムの一つで、隣り合う要素を比較しながらソートします。また、アルゴリズムが単純でプログラミングの学習によく用いられているそうです。

ソートの準備

バブルソートのプログラムを作る前に、ソートする配列を作らなければなりません。そこで、要素数Nのランダムな整数型の配列を生成するプログラムを作成しました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i;
    int N = 100;
    int n[N];

    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }
}

これで生成されるランダムな配列に対してソートを行ってみたいと思います。

マージソートのプログラム

マージソートのプログラムを次のように作ってみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i,j,t;
    int N = 10;
    int n[N];

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // 配列を表示
    printf("ソート前: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");

    // バブルソート
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }

    // 配列を表示
    printf("ソート後: ");
    for(i=0; i<N; i++){
        printf("%d ",n[i]);
    }
    printf("\n");
}

とりあえず確認のため要素数Nを10で実行してみると次の結果が得られました。

ソート前: 3362 5885 7590 2004 2490 2836 6035 697 7675 5956
ソート後: 697 2004 2490 2836 3362 5885 5956 6035 7590 7675

きちんとソートされているのが確認できました。

マージソートの実行時間を測る

プログラムを次のように変更し、マージソートの実行時間を測ってみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i,j,t;
    int N = 10000;
    int n[N];
    clock_t start, end;

    // ランダムな配列を生成
    srand(time(NULL));
    for(i=0; i<N; i++){
        n[i] = rand() % 10000;
    }

    // バブルソート
    start = clock();
    for(i=0; i<N-1; i++){
        for(j=i+1; j<N; j++) {
            if(n[j] < n[i]){
                t = n[j];
                n[j] = n[i];
                n[i] = t;
            }
        }
    }
    end = clock();

    printf("要素数: %d\n", N);
    printf("バブルソート実行時間: %f sec\n", (double)(end-start)/CLOCKS_PER_SEC);

}

これをコンパイルして実行すると、大体0.33秒あたりとなりました。この値は使っているコンピュータに依存してくると思います。 また、生成される配列は毎回異るので、実行するごとに実行時間が異なってしまいます。 要素数を増やしていくとどのような、相関があるのか気になったため、何回か実行した平均値をとって見たいと思います。 プログラムを次のようにしてみました。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int main(void) {
    int i,j,k,t;
    int N = 10000; //配列の要素数
    int M = 10; //実行回数
    int n[N];
    clock_t start, end;
    double total = 0.0; //各実行時間の和
    struct timeval tv;

    for(k=0; k<M; k++){
        // ランダムな配列を生成
        gettimeofday(&tv,NULL);
        srand(tv.tv_sec * tv.tv_usec);
        for(i=0; i<N; i++){
            n[i] = rand() % 10000;
        }

        // バブルソート
        start = clock();
        for(i=0; i<N-1; i++){
            for(j=i+1; j<N; j++) {
                if(n[j] < n[i]){
                    t = n[j];
                    n[j] = n[i];
                    n[i] = t;
                }
            }
        }
        end = clock();
        total += (double)(end-start)/CLOCKS_PER_SEC;
    }

    printf("要素数: %d\n", N);
    printf("実行回数: %d\n", M);
    printf("バブルソート平均実行時間: %f sec\n", total/M);

}

ランダムな配列を生成するときに、乱数の種の生成はsrand(time(NULL))を使っていました。 しかし、これでは乱数の種は秒単位で変わるので、今回のプログラムには適していません。 そこで、更に細かい時間で乱数の種を生成できるように、上記のようにしてみました。 さらに、バブルソートの実行回数は10回としており、収束が悪いですが、時間の都合上これで行い、 有効数字を2桁でとってみます。 自分のノートパソコンでの結果は次の通りになりました。(データはかなり雑です)

配列の要素数 : 平均の実行時間(秒)
1000 : 0.0027
10000 : 0.35
100000 : 20

素数増えると実行時間結構かかりました。図でも書こうかと思いましたけどやめました。

C言語でプログラムの実行時間を測る

プログラムの実行時間を測りたい

C言語でソートのプログラムを作ってテストしたいなと思いました。 せっかく作るなら実行時間を測って、ソートのアルゴリズムの性能を評価してみたいと思います。 そこで、今回の記事ではC言語での、実行時間の測り方をまとめてみたいと思います。

clock()を使う

C言語ではプログラム実行時からの時間を取得することができるclock()があります。 実行時間を測定したいところの前でclock()を実行し、それが終了するところで再びclock()で時間を取得し それらを引けば実行時間を得ることができます。また、clock()を使うには、 time.hのヘッダファイルをインクルードする必要があります。 次にサンプルを書いてみました。

#include <stdio.h>
#include <time.h>

int main(void) {
    clock_t start, end;
    start = clock();

    int i;
    for(i = 0; i < 1000000; i++){
    }

    end = clock();
    printf("%f sec\n", (double)(end-start)/CLOCKS_PER_SEC);

}

テストなので、何もしないforループを回して時間をかけました。また、秒で表示するためにはCLOCKS_PER_SECで割る必要があります。 さらにdouble型でキャストしました。

これでアルゴリズムの処理時間が測定できそうです。

C言語でじゃんけんゲームをつくる(switch文、while文を使う)

C言語でじゃんけんゲーム

C言語で簡単なじゃんけんをするゲームを作ってみたいと思います。また、プログラムを作る中でswitch文も使ってみます。

switch文を使ってみる

switch文とは条件に応じて処理を分ける構文です。入力された文字に対して処理を変えるプログラムを次のようにつくってみました。

#include <stdio.h>

int main(void) {
    int d;
    printf("手を入力してください(グー:1, チョキ:2, パー:3): ");
    scanf("%d",&d);
    switch(d){
        case 1:
            printf("グーです\n");
            break;
        case 2:
            printf("チョキです\n");
            break;
        case 3:
            printf("パーです\n");
            break;
        default:
            printf("正しく入力できていません\n");
            break;
    }
    return 0;
}

このプログラムではキーボードからの入力(1か2か3かその他)におうじて表示内容を変えています。このプログラムのswitch文では、"switch"に続くカッコ内の変数"d"と"case"のあとに続く数字が一致しているかどうかで実行されます。もし、"case"に続く数字と一致していればその"case"ないの文が実行され、"break"によって抜けます。どれとも一致するものがなければ最後に書いてある"default"が実行されます。

while文でループさせてみる

次に対戦回数を入力させ、その回数分switch文をループさせてみたいと思います。ループをする方法にはfor文やwhile文があると思いますが、今回はwhile文を使って以下のようにしてみました。

#include <stdio.h>

int main(void) {
    int i = 0;
    int d,n;
    printf("何回対戦しますか?: ");
    scanf("%d",&n);

    while (i < n) {
        printf("手を入力してください(グー:1, チョキ:2, パー:3): ");
        scanf("%d",&d);
        switch(d){
            case 1:
                printf("グーです\n");
                break;
            case 2:
                printf("チョキです\n");
                break;
            case 3:
                printf("パーです\n");
                break;
            default:
                printf("正しく入力できていません\n");
                break;
        }
        i++;
    }
    return 0;

while文ではwhileの後ろのカッコの中の条件が、真の限りループが回り続けます。

コンピュータにランダムな手を入力させる

コンピュータにランダムな手を入力させるため、まず1~3の乱数を生成します。C言語で乱数を生成するにはrand()を使います

srand(time(NULL));
int r = rand() % 3 + 1;

rand()を使うためには"stdlib.h"を読み込む必要があります。また、srand()で乱数を初期化するときにtime()を使うので、"time.h"も読み込みます。

じゃんけんゲームをつくってみる

次のようにじゃんけんゲームをつくってみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i = 0;
    int n,d;
    int win = 0;
    printf("何回対戦しますか?: ");
    scanf("%d",&n);

    while (i < n) {
        srand(time(NULL));
        int cpu = rand() % 3 + 1; 

        printf("手を入力してください(グー:1, チョキ:2, パー:3): ");
        scanf("%d",&d);
        switch(d){
            case 1:
                if (cpu == 1) {
                    printf("あいこ (あなた:グー, コンピュータ:グー)\n");
                }
                if (cpu == 2) {
                    printf("勝ち (あなた:グー, コンピュータ:チョキ)\n");
                    win++;
                }
                if (cpu == 3) {
                    printf("負け (あなた:グー, コンピュータ:パー)\n");
                }
                break;
            case 2:
                if (cpu == 1) {
                    printf("負け (あなた:チョキ, コンピュータ:グー)\n");
                }
                if (cpu == 2) {
                    printf("あいこ (あなた:チョキ, コンピュータ:チョキ)\n");
                }
                if (cpu == 3) {
                    printf("勝ち (あなた:チョキ, コンピュータ:パー)\n");
                    win++;
                }
                break;
            case 3:
                if (cpu == 1) {
                    printf("勝ち (あなた:パー, コンピュータ:グー)\n");
                    win++;
                }
                if (cpu == 2) {
                    printf("負け (あなた:パー, コンピュータ:チョキ)\n");
                }
                if (cpu == 3) {
                    printf("あいこ (あなた:パー, コンピュータ:パー)\n");
                }
                break;
            default:
                printf("\n正しく入力できていません。プログラムを終了します\n");
                return 0;
        }
        i++;
    }
    printf("対戦回数 %d回  勝数 %d\n", n, win);
    return 0;
}

対戦回数と勝数を数えて最後に表示するようにしてみました。

C言語で関数を使う

C言語の関数とは

C言語で関数とは、ある一通りの処理をまとめたものです。今まで使ってきた"main()“や"printf()"も実は関数です。"main()"以外にも自分で関数を定義し、使っていくことができます。今回はC言語で関数を定義し、実際に使ってみたいと思います。

簡単な関数をつくってみる(void型)

はじめに、与えられた整数型の数字を足して、"printf()“で表示するプログラムを作ってみました。

include <stdio.h>

void sum(int d1, int d2){
    printf("%d\n", d1+d2);
}

int main(void){
    sum(2,4);
    return 0;
}

この中で、自分で定義した関数は"void sum(int d1, int d2)“です。関数を定義するときはこのようにします。関数を定義するときの注意点としては、プログラムは上から順にコンパイラに解析されていくので、実行するところよりも上に書いてないといけないことです。もし、実行するところよりもあとに書きたいときは関数原型宣言(関数プロトタイプ宣言)をしなければなりません。これについては後で説明いたします。

上記のプログラムでは"sum()“をvoid型で宣言しました。void型は返り値がない関数です。この関数ではint型のd1、d2を引数として受け取っています。引数とは、関数を利用する際に、実行する関数に与えることができる値です。引数は関数の中で利用することができます。この関数は"main()"の中で"sum(2,4)"と関数を呼び出し、関数に渡した二つの引数を足して表示しています。

簡単な関数をつくってみる(int型)

今度は、先程の関数をvoid型ではなく、int型の返り値を持つ関数で作ってみます。次のようにしてみました。

#include <stdio.h>

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

この関数"sum()“では"void"となっていたところが"int"となっています。これは返り値はint型ですよ、という意味です。"main()"を見てみると、"x = sum(2,4)"となっており、"sum()"が実行され、返ってくる値を"x"に代入しています。そして、得られたxを"printf()"で表示しています。

関数原型宣言(プロトタイプ宣言)をやってみる。

ここで、次のプログラムをコンパイルしてみます。

#include <stdio.h>

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

gccコンパイルしてみましたが、以下のような警告がでました。

test.c:5:9: warning: implicit declaration of function 'sum' is invalid in C99 [-Wimplicit-function-declaration]
    x = sum(2,4);
        ^
1 warning generated.

自分としては、コンパイルできないのかなと思っていましたが、コンパイルができ実行もできました。警告は"sumが宣言されてないけど、C99では無効だよ"って意味です。コンパイラによってはコンパイルできないみたいです。この警告を消すためにプログラムを次のようにしてみました。

#include <stdio.h>

int sum(int, int);

int main(void){
    int x;
    x = sum(2,4);
    printf("%d\n",x);
    return 0;
}

int sum(int d1, int d2){
    int ans;
    ans = d1 + d2;
    return ans;
}

main()の前に"int sum(int d1, int d2);“の行が追加されています。これが関数原型宣言です。こういう型の関数を宣言するよ、というのを先にコンパイラに教えておきます。関数原型宣言ではカッコ内の引数の"d1"、"d2"などの変数名は必要なく、型だけでオッケーです。

再帰関数をつくってみる

次に、再帰関数というものを作ってみたいと思います。今まで、関数を"main()“の中から呼び出していました。宣言した関数の中で、さらにその関数自身を呼び出すとどうなるのでしょうか。そのように、関数の中で自分自身の関数を呼び出す関数を再帰関数と呼びます。

階上の再帰関数をつくってみる

はじめに単純な例である、階上の再帰関数をつくってみます。例えば4の階上は

4! = 4 × 3 × 2 × 1 = 24

となります。そこで次のようなプログラムを作ってみました。

#include <stdio.h>

int factorial(int n){
    if (n == 1){
        return n;
    } else {
        return n * factorial(n - 1);
    }
}

int main(void){
    int x;
    x = factorial(4);
    printf("%d\n",x);
    return 0;
}

このプログラムの中で"factorial()“という関数が再帰関数として書かれています。この関数の中で、"return n * factorail(n-1)"という行があります。この行で自分自身が呼び出されています。階上では数字を1づつ減らしながら1まで掛けていきます。なので、"n"がイチのとき、関数を呼び出さず値を返してあげ、それ以外は、"n-1"をもとの数と掛けていきます。理解しやすくするため、"factorial()"を次のようにしてみました。

int factorial(int n){
    int x;
    if (n == 1){
        x = n;
        printf("factorial: %d\n",x);
        return x;
    } else {
        x =  n * factorial(n - 1);
        printf("factorial: %d\n",x);
        return x;
    }
}

実行結果↓

factorial: 1
factorial: 2
factorial: 6
factorial: 24
answer: 24

はじめに表示されている値は"1"です。"main()“の中で、関数に渡した値は4なのにはじめに"1"が表示されます。これは"printf()"を通過する前に"factorial(n-1)"が呼び出されているので、値が表示される前に、さらに関数が呼び出されるためです。"n == 1"までいくと、値が返ってくるのでその下の"printf()"が実行されていきます。そして、はじめは1、その後1×2=2、2×3=6、6×4=24というのが表示されていきます。

等比数列の和の再帰関数をつくってみる

次に等比数列の和を再帰関数で求めてみたいと思います。

等比数列 - Wikipedia

別に再帰関数を書かなくても、公式を使えばすぐできますが、練習のため作ってみました。また、等比数列の和を求める中で、累乗を求める必要があります。C言語の数学的な計算をするための"math.h"のヘッダの中に、累乗を計算する"pow()“が定義されていますが、今回はこれも自分で作って見ました。"math.h"で定義されている"pow()"はdouble型の返り値を持ちますが、今回つくってみたのはint型ですのでご注意ください。

#include <stdio.h>

int pow(int a, int n) {
    int ans = 1;
    int i;
    for(i=0; i<n; i++){
        ans = ans*a;
    }
    return ans;
}

int geoprog(int a, int r, int n) {
    if (n == 1) {
        return a;
    } else {
        return a*pow(r,n-1) + geoprog(a, r, n-1);
    }
}

int main(void){
    int x;
    x = geoprog(1,2,5);
    printf("answer: %d\n",x);
    return 0;
}

等比数列の和を求める関数は"geoprog()“です。引数は"a"が初項、"r"が項比、"n"が項数です。"初項1,公比2,項数5"で実行すると"31"とでてきたので、おそらくあっていると思います。ちなみに、"pow()"は引数"a"が底で、"n"が指数です。ちなみに、"pow()"はint型で作っているので、"n"が負の数になるような場合はきちんと動きません。"n"を負の数にも対応させたいときはdouble型になるように作ってみてください。

Python3で標準入力(input())

Python3で標準入力

Python3で標準入力をしたいときはinput()を使います。競技プログラミングなどでPython3を使うとき、標準入力ができないと問題を解くことができません。今回は標準入力の仕方を見ていきます。

試しにinput()を使ってみる。

はじめに次のプログラムを実行してみました。

s = input()
print(s)

これを実行すると何も表示されませんが、文字列を入力しEnterキーを押すと、入力された文字列がそのまま表示されます。

空白文字で区切られた文字列をリストにする

次に、競技プログラミングでよくある、空白文字で区切られた文字列を読み込むことを行ってみます。以下のようなプログラムにしてみました。

s = input()
s = s.split()
print(s)

実行結果↓

1 2 3 4 5 6
['1', '2', '3', '4', '5', '6']

上の行は自分で打った入力です。下の行は出力です。split()で文字列が分割されていることがわかります。 しかし、数字は文字列のリストとなっていますので整数型にしたいです。 文字列が数字で入力されるという前提で、これらを整数型にしてみます。

s = s.split()
n = []
for i in s:
    n.append(int(i))
print(n)
1 2 3 4 5 6
[1, 2, 3, 4, 5, 6]

整数型のリストができたみたいです。次にfor文ではなく、リスト内包表記で書いてみると次のようになると思います。

n = [int(x) for x in input().split()]
print(n)

シンプルに書くことができました。このプログラムではまずinput()で受け取った入力をすぐにsplit()で分割し、リストを得ます。そのリストの要素一つ一つに対して、リスト内包表記でxとして取り出しint()でキャストしています。

複数の入力を受け取る

競技プログラミングでは1番目の行で要素の数、その後複数の行の読み込み、などもあると思います。そのようなときはその分input()の行を書いてあげればいいと思います。 はじめに文字列を受け取る次のようなプログラムを書いてみました。

N = int(input())
s = [input().split() for i in range(N)]
print(s)

入出力例↓

3  #入力 行の数
hoge piyo piyo  #入力
piyo piyo piyo  #入力
hoge hoge hoge  #入力
[['hoge', 'piyo', 'piyo'], ['piyo', 'piyo', 'piyo'], ['hoge', 'hoge', 'hoge']]  #出力

実際には#入力 #出力を書く必要はありません。入力された文字列を最初の入力の行の数だけ、二重のリストに入れることができました。

始めに入力される行の数、次の行からその分の整数の列が入力されると考えて、以下のようなプログラムを作ってみました。

N = int(input())
n = [list(map(lambda x:int(x),input().split())) for i in range(N)]
print(n)

入出力例↓

3  #入力 列の数
1 2 3 4 5  # 入力
5 4 3 2 1  # 入力
1 1 2 2 3  #入力
[[1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [1, 1, 2, 2, 3]]  #出力

少し複雑になってしまいましたが、複数の入力を二重のリストをint型にキャストしながら作ることができました。

C言語でいろいろな形の図を"*"で表示してみる(for文を入れ子にしてみる)

C言語で"*“を使って図を書いてみる

C言語で、"*“の記号を使っていろいろな図を書くことに挑戦してみたいと思います。また、図を書くにために、for文を入れ子(ネスト)にしてみたいと思います。

for文の入れ子

まずfor文の入れ子の動作を確認してみたいと思います。次のプログラムを実行してみます。

int main(void){
    int i,j;

    for(i=0; i<5; i++) {
        for(j=0; j<3; j++) {
            printf("i:%d, j:%d\n", i, j);
        }
    }
}

結果↓

i:0, j:0
i:0, j:1
i:0, j:2
i:1, j:0
i:1, j:1
i:1, j:2
i:2, j:0
i:2, j:1
i:2, j:2
i:3, j:0
i:3, j:1
i:3, j:2
i:4, j:0
i:4, j:1
i:4, j:2

iとjがどのように変わっているのか確認するプログラムです。結果を見てみると、外側のループが実行され、次に中のループが実行され、終了すると再び外側のループに戻り、そして再び中のループが実行されていることが分かります。

四角形を"*“で書いてみる

次にfor文の入れ子を使って四角を書いてみます。

int main(void){
    int i,j;

    for(i=0; i<5; i++) {
        for(j=0; j<5; j++) {
            printf("*");
        }
        printf("\n");
    }
}

結果↓

*****
*****
*****
*****
*****

このプログラムでは内側のループで改行なしで"*“を打ちます。そうすると

*****

が表示されます。内側のループを抜け、外側のループに戻るときに改行"\n"します。そうすることによって"*****“を繰り返し書くことができ、四角になります。

三角形を"*“で書いてみる

次に、三角形を描いてみます。プログラムを次のように書いてみました。

#include <stdio.h>

int main(void){
    int i,j;

    for(i=0; i<5; i++) {
        for(j=0; j<=i; j++) {
            printf("*");
        }
        printf("\n");
    }
}

結果↓

*
**
***
****
*****

たぶんできました!printf()のところは変えていません。内側のfor文の条件のところを変えました。

j<=i;

とすることによって、jがiと同じ数より大きくなったときだけfor文が実行されます。つまり、iと同じ数だけ内側のfor文のループが回ります。

次に、三角形の上の頂点が右になったものをif文を使いならが書いてみます。 プログラムを次のようにしてみました。

#include <stdio.h>

int main(void){
    int i,j;

    for(i=0; i<5; i++) {
        for(j=5; j>0; j--) {
            if (j-i > 1) {
                printf(" ");
            } else {
                printf("*");
            }
        }
        printf("\n");
    }
}

結果↓

    *
   **
  ***
 ****
*****

まぁできました。外側のループは一緒ですが、内側のループでjが5,4,3,2,1となるようにしました。 するとj-iの値が、次のようになります。

i:0, j-i: 5,  4,  3,  2,  1
i:1, j-i: 4,  3,  2,  1,  0
i:2, j-i: 3,  2,  1,  0, -1
i:3, j-i: 2,  1,  0, -1,  1
i:4, j-i: 1,  0, -1, -2, -3

なので、j-1の値が1より大きいときに" “を、1以下のときに”*“を書くようにするとできました!

もっと別な図形を書くことに挑戦してみたいですね。