C言語教室 解答編 第27回 - と、C言語の良いところ
今回はマージソートです。マージソートってデータを分割して、それぞれをソートしてから、ソート済みのデータを結合していくものです。
C言語教室 第27回 いろいろなソート(続)
普通は再帰を使うので自分で自分を呼んで、グルグル回って処理を進めるので、なんだか目が回りますよね。教室ではリスト構造のソートを取り上げましたが、ソートというと配列をソートすることが多いのですが、リストのソートもなかなか頭を捻るところがあって、よい練習になります。
さてさて、まだ課題をやっていないという方は、是非、挑戦をしてください。また結果をお知らせいただけたら幸いです。締切は設けていないので、挑戦したらぜひお知らせください。
まだ課題を解いていないという方が、うっかり解答を見ないための閑話です。今回はC言語の良さってなんだろということを書いてみます。
プログラムを書けるようになるというのは、プログラミング言語を使いこなすことができる必要があるのはもちろんですが、言語はあくまで手段であって、大事なことは目的の処理を、どう分解して正しく実行できるようにするのかという部分です。
そのためにアルゴリズムとかライブラリを覚えることが必要ですし、それらを使うためにもいろいろな概念を学ぶ必要があります。C言語はかなりCPUが理解するマシン語に近い言語ですし、言語でいろいろなことをやってくれないので、自分で理解してコードを読んだり書いたりする必要があります。もっとモダンな言語では自動的にやってくれるようなことを、いちいち書いていくことになるのですが、そうすることでCPUが実際に何をやっているかを理解することが出来ます。C言語を理解することで少しでも「CPUの気持ち」がわかるようになれば、思った動作にならなかったり、ヤケに遅いという場合に、その理由が見えてくるのではと思います。
最近はlinuxのカーネルでもC言語ではなくRustが使われるようになってきましたが、殆どのシステムはC言語かアセンブラ(マシン語)で書かれています。Javaでもpythonでも結局はC言語なんです。ですからC言語が読めるようになれば、こういった言語処理系自身のコードを理解できるようになります。そういったコードは決して読みやすいものではないのですが、ある処理をするには、どのようにプログラムを書いていけば良いのかの素晴らしい生きた教材です。
では課題に進みましょう。
課題
1. 整数と文字列を持つ構造体のリストを用意して、整数での並べかえと文字列での並べかえを、それぞれ昇順でマージソートする関数を書きなさい。
2. 文字列（ポインタの）配列をマージソートする関数を書きなさい。
最初の課題は、教室で説明したコードを元にして文字列に対するコードを追加すればOKです。整数と文字列の関数を共通にしてみようとも考えたのですが、引き数の型が異なってしまうので、アクロバティックなことをしないと共通に出来ないことに気がついたので素直に文字列用の関数を加えることにしました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ノードの構造体 */
typedef struct node {
int val;
char *str;
struct node* next;
} Node;
/* 連結リストの表示 */
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d,%s ", temp->val, temp->str);
temp = temp->next;
}
printf("\n");
}
/* 連結リストを分割する */
void splitList(Node* source, Node** frontRef, Node** backRef) {
Node* slow;
Node* fast;
/* 分割位置を見つける */
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
/* slowを分割位置として設定 */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
/* 連結リストをマージする(整数) */
Node* merge_int(Node* a, Node* b) {
Node* result = NULL;
/* ベースケース：どちらかのリストが空の場合 */
if (a == NULL)
return b;
else if (b == NULL)
return a;
/* どちらのリストの先頭のデータが小さいか比較し、再帰的にマージする */
if (a->val <= b->val) {
result = a;
result->next = merge_int(a->next, b);
} else {
result = b;
result->next = merge_int(a, b->next);
}
return result;
}
/* 連結リストをマージソートする(整数) */
void mergeSort_int(Node** headRef) {
Node* head = *headRef;
Node* a;
Node* b;
/* ベースケース：リストが空または1つの要素しかない場合 */
if (head == NULL || head->next == NULL)
return;
/* 連結リストを分割する */
splitList(head, &a, &b);
/* 分割したリストを再帰的にマージソートする */
mergeSort_int(&a);
mergeSort_int(&b);
/* マージしてソートしたリストを再接続する */
*headRef = merge_int(a, b);
}
/* 連結リストをマージする(文字列) */
Node* merge_str(Node* a, Node* b) {
Node* result = NULL;
/* ベースケース：どちらかのリストが空の場合 */
if (a == NULL)
return b;
else if (b == NULL)
return a;
/* どちらのリストの先頭のデータが小さいか比較し、再帰的にマージする */
if (strcmp(a->str, b->str) <= 0) {
result = a;
result->next = merge_str(a->next, b);
} else {
result = b;
result->next = merge_str(a, b->next);
}
return result;
}
/* 連結リストをマージソートする(文字列) */
void mergeSort_str(Node** headRef) {
Node* head = *headRef;
Node* a;
Node* b;
/* ベースケース：リストが空または1つの要素しかない場合 */
if (head == NULL || head->next == NULL)
return;
/* 連結リストを分割する */
splitList(head, &a, &b);
/* 分割したリストを再帰的にマージソートする */
mergeSort_str(&a);
mergeSort_str(&b);
/* マージしてソートしたリストを再接続する */
*headRef = merge_str(a, b);
}
/* 連結リストに要素を追加する */
void push(Node** headRef, int newval, char *newstr) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->val = newval;
newNode->str = newstr;
newNode->next = (*headRef);
(*headRef) = newNode;
}
void main() {
Node* head = NULL;
/* テスト用のデータを追加 */
push(&head, 9, "apple");
push(&head, 5, "orange");
push(&head, 9, "greenapple");
push(&head, 2, "grape");
push(&head, 7, "banana");
push(&head, 3, "peach");
/* 連結リストをマージソートする(整数) */
printf("Origin:");
printList(head);
mergeSort_int(&head);
printf("Result:");
printList(head);
printf("\n");
/* 連結リストをマージソートする(文字列) */
printf("Origin:");
printList(head);
mergeSort_str(&head);
printf("Result:");
printList(head);
}このコードでの結果は以下です。
Origin:3,peach 7,banana 2,grape 9,greenapple 5,orange 9,apple
Result:2,grape 3,peach 5,orange 7,banana 9,greenapple 9,apple
Origin:2,grape 3,peach 5,orange 7,banana 9,greenapple 9,apple
Result:9,apple 7,banana 2,grape 9,greenapple 5,orange 3,peach 文字列でソートする時の元データが整数でソート済みのものを再利用していますが、そこは許してください。整数と文字列で比較の部分が異なる以外は同じ処理です。
次の課題は配列をソートするものです。配列のマージソートは既成のコードがたくさんあると思いますが、文字列をソートするときに、どの部分を変えていけば良いのかを確認していくことで、単なるコピペではなくちゃんと理解できるのではないかと思います。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void merge(char** arr, int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
char** ls = (char**)malloc(n1 * sizeof(char*));
char** rs = (char**)malloc(n2 * sizeof(char*));
for (i = 0; i < n1; i++)
ls[i] = arr[left + i];
for (j = 0; j < n2; j++)
rs[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (strcmp(ls[i], rs[j]) <= 0) {
arr[k] = ls[i];
i++;
} else {
arr[k] = rs[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = ls[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rs[j];
j++;
k++;
}
free(ls);
free(rs);
}
void merge_sort(char** arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void main() {
char* arr[] = {"apple", "banana", "orange", "grape", "cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
int i;
printf("Original array: ");
for (i = 0; i < n; i++)
printf("%s ", arr[i]);
printf("\n");
merge_sort(arr, 0, n - 1);
printf("Sorted array: ");
for (i = 0; i < n; i++)
printf("%s ", arr[i]);
printf("\n");
}このコードを実行すると以下の出力が得られます。
Original array: apple banana orange grape cherry
Sorted array: apple banana cherry grape orange ポイントはくれぐれも文字列自身を動かさずに、文字列へのポインタを入れ替えてソートしていくことです。文字列のポインタを扱うので今回もダブルポインタが登場しますが、どうしても難しいと思ったら、typedef で charptr という型を作って書き直してみてください。
(2023.6.16追記)
AyumiKatayama さんから答案をいただくことが出来ました。とりあえず最初の課題のみですが、興味深く読ませていただきました。
C言語教室 第27回 いろいろなソート(続)（回答提出）(1)
双方向循環リストを使ってマージソートを書いていただきました。さらに再帰を使わずループの形にしたうえで、文字列に関しても固定長配列を使い、メモリ使用量を予測可能な形に収めたアタリ、なかなか組み込み系での経験がうかがえます。
初期データとして、可変長であるC文字列の配列から固定長のリスト内の文字配列に strncpy をしてリストを初期化しています。ソートの際にはリストを繋ぎ変えていくので、この固定長の文字列をコピーすることはないので、構わないわけですね。
細かいところで恐縮ですが、最初に strncpy するときに初期データの最後の文字列に対して、オーバーランしないか見てみたのですが、strncpy はソース文字列の終端を見つけるとコピーを打ち切り、コピー先の残りの領域には'\0'を埋めるので、大丈夫なようでした。但し、初期データの各々の文字列長がリスト内の固定長を超えた場合、最後に'\0'が付加されないので、ソート自身は strncmp なので正しく行われるのですが、表示する際に問題が出るようです。
(2023.7.21追記)
残りの課題についても答案を頂きました。忘れないで頂けて感謝です。ハイ、いくらでも待ちますので、お時間の出来たときにでも課題に挑戦していただければ幸いです。
C言語教室 第27回 いろいろなソート(続)（回答提出）(2)
よろしければ、私の書いたコードとの違いなんかを解説していただければ幸いです^^;。
まだまだ答案は募集中です。もう次の課題も出てしまいましたが、順序は問いませんので、お時間が出来たときに是非とも挑戦してみてください。
どうも Bing も Bard もC言語のソースコードの品質が悪いです。どうしてChatGPT との差が出るのか不思議なのですが、ベースになる学習対象がそんなに違うのでしょうか。その意味で CharGPT は使ってはいけないコードを読んでいないか少し心配です。
次回はクイックソートです。
ヘッダ画像は、いらすとや さんより
https://www.irasutoya.com/2020/04/blog-post_243.html