久しぶりに勉強したら非道い… - 元データ分析の会社で働いていた人の四方山話

タイトル通りのひどさMAX。
今の仕事ではコードを読んだり修正をすることがほとんどで、自分で一からコードを書くことがないからどんどん忘れていってる。
これはやはいので少しずつでもリハビリしていく。

とりあえず、本棚にあったアルゴリズムの本を引っ張りだして、読むことに決めた。

プログラミングの宝箱アルゴリズムとデータ構造 (C magazine)
	ソフトバンククリエイティブ 2003-06-14 売り上げランキング : 99816 おすすめ平均初級者が中上級者になるためのよいガイド初心者にやさしいプログラミング解説本 Amazonで詳しく見る by G-Tools

バブルソート

まずはバブルソート

先頭から最後まで順に見ていく
見ている場所を起点として、一つ隣を見て、左右で並びがおかしなところがあれば入れ替える

と記憶していたが、さすがアルゴリズムの本、一工夫して、

１度も並べ替えをすることなく先頭から最後まで見終わったら、整理完了

というステップが追加されていた。
確かにこれなら、並び終わっているのに最後まで要素を見ていくという処理が省略できるね。

とりあえず写経

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

#define N 10

int sort[N];

void BubbleSort(void)
{
  int i, j, flag;
  do {
    flag = 0;
    for (i = 0; i < N-1; i++) {
      if (sort[i] > sort[i+1]) {
        flag = 1;
        j = sort[i];
        sort[i] = sort[i+1];
        sort[i+1] = j;
      }
    }
  } while(flag == 1);
}

int main(void)
{
  int i;
  srand((unsigned int)time(NULL));

  printf("ソート準備:\n");
  for (i = 0; i < N; i++) {
    sort[i] = rand();
    printf("%d ", sort[i]);
  }

  printf("\nソート開始:\n");
  BubbleSort();

  printf("\nソート完了:\n");

  for (i = 0; i < N; i++) {
    printf("%d ", sort[i]);
  }

  return EXIT_SUCCESS;
}

うん、rand()で得られる値が大きすぎて、結果がすごく見にくい。
任意の範囲で乱数を得られる方法があったはずなので、それを調べるとする。
あと、returnで返してる値がなんだったっけ？という話。
何かいろいろ忘れている…

任意乱数を得る方法

参考というかまんま。
乱数

rand();

の部分を、

最小値 + (int)(rand() * (最大値 - 最小値 + 1.0) / (1.0 + RAND_MAX))

とするような関数

int GetRandom(int min,int max)
{
	return min + (int)(rand()*(max-min+1.0)/(1.0+RAND_MAX));
}

って感じのものを作ってあげれば良いってことですね。
ついでなんで、ちょっとだけ引数を変えて、0から任意の数までの乱数を返すようにしました。

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

#define N 10

int sort[N];

void BubbleSort(void)
{
  int i, j, flag;
  do {
    flag = 0;
    for (i = 0; i < N-1; i++) {
      if (sort[i] > sort[i+1]) {
        flag = 1;
        j = sort[i];
        sort[i] = sort[i+1];
        sort[i+1] = j;
      }
    }
  } while(flag == 1);
}

int GetRandom(int max)
{
  return 0.0 + (int)(rand() * (max - 0.0 + 1.0) / (1.0 + RAND_MAX));
}

int main(void)
{
  int i;
  srand((unsigned int)time(NULL));

  printf("ソート準備:\n");
  for (i = 0; i < N; i++) {
    //sort[i] = rand();
    sort[i] = GetRandom(10*N);
    printf("%d ", sort[i]);
  }

  printf("\nソート開始:\n");
  BubbleSort();

  printf("\nソート完了:\n");

  for (i = 0; i < N; i++) {
    printf("%d ", sort[i]);
  }

  return EXIT_SUCCESS;
}

という感じに
結果は

% ./a.out
ソート準備:
52 97 10 50 66 36 96 35 56 94 
ソート開始:

ソート完了:
10 35 36 50 52 56 66 94 96 97

うん、見やすくなった。

えーと、次はRAND_MAXと、EXIT_SUCCESSを調べる予定。
ホントはこれをRubyで書き換えて、とかしたいんだけど、いつになったらそこに辿り着くんだ…