プログラミング言語 C

lang

クイックソートプログラムを 次の本を参考に 実際に動かしてみた。
「基礎Ｃ言語」(isbn:4000078569) p192-197


初めに q_sort.c ファイルに ちょっと コードを追加、

  1. /* quick_sort.c */
  2. #include
  3. void q_sort();
  4. void swap();
  5. void quick_sort(int a[], int n)
  6. {
  7. q_sort(a, 0, n); /* left の値に 前もって 0 を入れておく */
  8. }
  9. void q_sort(int v[], int left, int right)
  10. {
  11. int i;
  12. int last;
  13. if (left >= right)
  14. return;
  15. swap(v, left, (left + right)/2);
  16. last = left;
  17. for (i = left + 1; i <= right; i++)
  18. if (v[i] < v[left])
  19. swap(v, ++last, i);
  20. swap (v, left, last);
  21. q_sort(v, left, last - 1);
  22. q_sort(v, last + 1, right);
  23. }
  24. void swap(int v[], int i, int j)
  25. {
  26. int tmp;
  27. tmp = v[i];
  28. v[i] = v[j];
  29. v[j] = tmp;
  30. }

次は 読み込み用の read_array.c ファイル、

  1. /* read_array.c */
  2. #include
  3. int read_array(int a[], int limit)
  4. {
  5. int n = 0;
  6. printf("Input whole numbers upto %d.\n", limit);
  7. printf("standard input:[enter][ctrl+d]\n");
  8. /*上の 2行は説明文のため、コメントアウトしても OK */
  9. while (n < limit && scanf("%d", &a[n]) != EOF)
  10. ++n;
  11. return --n; /* 初期値分を 1つ減らしておく */
  12. }

ソートの結果を出力する print_array.c ファイル、

  1. /* print_array.c */
  2. #include
  3. void print_array(int a[], int n)
  4. {
  5. int i;
  6. for (i = 0; i <= n; i++) {
  7. printf("%3d ", a[i]);
  8. if ((i + 1) % 10 == 0) { /* データは 1行に 10個ずつ出力 */
  9. putchar('\n');
  10. }
  11. }
  12. if (i % 10 != 0) /* この i は 全データ数 */
  13. putchar('\n');
  14. }

関数 main() ファイル、これは 簡単に、

  1. /* q_main.c */
  2. #include
  3. #include "q_header.h"
  4. /* クイックソートプログラム */
  5. main()
  6. {
  7. int a[MAX];
  8. int n; /* 全データ数 */
  9. n = read_array(a, MAX);
  10. quick_sort(a, n);
  11. print_array(a, n);
  12. return 0;
  13. }

最後に ヘッダファイルを作成、

  1. /* q_header.h */
  2. #define MAX 100
  3. int read_array();
  4. int print_array();
  5. void quick_sort();

コンパイルしてみます。まず オブジェクトファイルの作成。
cc -c q_main.c quick_sort.c read_array.c print_array.c
コンパイルエラーがあれば ここで訂正して、実行ファイルを作成。
cc -o q_sort q_main.o quick_sort.o read_array.o print_array.o


元になる 数字のリストですが、その前に、以前つくった random.c ファイルを 少し いじっておく。

  1. /* random.c */
  2. #include
  3. #include
  4. /* ランダムな数値のファイルを用意する */
  5. #define MAX 88
  6. struct List {
  7. int data;
  8. struct List *next;
  9. };
  10. main()
  11. {
  12. FILE *fp;
  13. int i;
  14. int seed;
  15. char buf[64];
  16. struct List *prev, *curr;
  17. prev = NULL;
  18. printf("Input seed = ");
  19. for ( ; scanf("%d", &seed) != 1 ; ) {
  20. printf("It's not finger. Input seed = ");
  21. scanf("%s", buf);
  22. }
  23. srand(seed);
  24. printf("OK, make 'random.txt' now.\n");
  25. fp = fopen("random.txt", "w");
  26. if (fp != NULL) {
  27. for (i = 0; i < MAX; i++) {
  28. curr = (struct List *)malloc(sizeof(struct List));
  29. fprintf(fp, "%d ", curr->data = rand() % 1000);
  30. curr->next = NULL;
  31. if (prev != NULL) {
  32. prev->next = curr;
  33. }
  34. prev = curr;
  35. }
  36. fprintf(fp, "\n");
  37. fclose(fp);
  38. }
  39. return 0;
  40. }

コンパイル後、$./random として 適当な数値を入力すると random.txt が 作成される。
$./q_sort < random.txt > sort.txt; cat sort.txt として 確認。