この記事では、C言語を使って配列を降順でマージソートする方法を学びます。
マージソートは、配列を小さな部分に分けてから順番に並べ直す効率的なソート方法です。
初心者の方でも理解しやすいように、アルゴリズムの基本から実際のコードの書き方まで、ステップバイステップで解説します。
これを読めば、C言語でのマージソートの仕組みと実装方法がわかるようになります。
マージソートのアルゴリズム
マージソートは、分割統治法を用いた効率的なソートアルゴリズムの一つです。
このアルゴリズムは、配列を再帰的に分割し、分割された部分をマージ(統合)することでソートを行います。
以下では、マージソートの基本的なアルゴリズムについて詳しく説明します。
分割
マージソートの最初のステップは、配列を分割することです。
配列を半分に分割し、それぞれの部分を再帰的にさらに分割していきます。
このプロセスは、配列の要素が1つになるまで続けられます。
分割の具体的な手順は以下の通りです。
- 配列の中央を見つける。
- 配列を中央で2つの部分に分ける。
- 各部分を再帰的に分割する。
例えば、配列 [38, 27, 43, 3, 9, 82, 10] を分割する場合、以下のように進行します。
- 元データ：[38, 27, 43, 3, 9, 82, 10]
- [38, 27, 43, 3] と [9, 82, 10] に分割
- [38, 27] と [43, 3] に分割
- [38] と [27] に分割
- [43] と [3] に分割
- [9] と [82, 10] に分割
- [82] と [10] に分割
マージ(統合)
分割された配列を再び統合する際に、要素を比較して順序を保ちながらマージします。
これにより、部分配列がソートされた状態で統合されます。
マージの具体的な手順は以下の通りです。
- 2つの部分配列の先頭要素を比較する。
- 小さい方の要素を新しい配列に追加する。
- 比較した要素を削除し、次の要素を比較する。
- すべての要素が新しい配列に追加されるまで繰り返す。
例えば、分割された配列 [38] と [27] をマージする場合、以下のように進行します。
- マージ対象のデータ：[38] と [27]
- 27 < 38 なので [27] を新しい配列に追加 => 残りの [38] を新しい配列に追加
- 結果: [27, 38]
再帰的な処理
マージソートは再帰的なアルゴリズムです。
つまり、分割とマージのプロセスが再帰的に呼び出されます。
再帰的な処理の流れは以下の通りです。
- 配列が1つの要素になるまで分割を繰り返す。
- 分割された部分配列をマージしてソートする。
- マージされた部分配列を再びマージして、最終的にソートされた配列を得る。
再帰的な処理の例として、配列 [38, 27, 43, 3, 9, 82, 10] をソートする場合を考えます。
- 元のデータ:[38, 27, 43, 3, 9, 82, 10]
- 分割: [38, 27, 43, 3] と [9, 82, 10]
- 分割: [38, 27] と [43, 3]
- 分割: [38] と [27]
- マージ: [27, 38]
- 分割: [43] と [3]
- マージ: [3, 43]
- マージ: [27, 38] と [3, 43]
- マージ: [3, 27, 38, 43]
- 分割: [9] と [82, 10]
- 分割: [82] と [10]
- マージ: [10, 82]
- マージ: [9] と [10, 82]
- マージ: [9, 10, 82]
- マージ: [3, 27, 38, 43] と [9, 10, 82]
- 最終結果: [3, 9, 10, 27, 38, 43, 82]
このようにして、マージソートは配列を効率的にソートします。
次のセクションでは、C言語でのマージソートの具体的な実装方法について説明します。
C言語でのマージソート実装
ここでは、C言語を用いて配列を降順でマージソートする方法を具体的に解説します。
まずは配列の初期化から始め、次にマージソート関数の実装、そしてメイン関数の実装を行います。
配列の初期化
まず、ソート対象となる配列を初期化します。
以下のコードは、整数型の配列を初期化する例です。
#include <stdio.h>
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("初期配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}このコードでは、配列 arr を初期化し、その要素数を計算して表示しています。
マージソート関数の実装
次に、マージソート関数を実装します。
マージソートは再帰的なアルゴリズムで、配列を分割し、分割された部分をマージしてソートします。
分割関数の実装
まず、配列を分割する関数を実装します。
この関数は、配列の左半分と右半分に分割し、それぞれを再帰的にソートします。
void mergeSort(int 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);
}
}この関数では、配列 arr を left から right までの範囲で分割し、再帰的にソートしています。
マージ関数の実装
次に、分割された部分をマージする関数を実装します。
この関数は、2つのソートされた部分を1つのソートされた配列にマージします。
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] >= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}この関数では、配列 L と R に分割された部分をコピーし、それらを降順でマージしています。
メイン関数の実装
最後に、メイン関数でマージソートを実行し、結果を表示します。
#include <stdio.h>
void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("初期配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
mergeSort(arr, 0, n - 1);
printf("ソート後の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}このメイン関数では、初期配列を表示し、マージソートを実行してからソート後の配列を表示しています。
以上で、C言語を用いた配列の降順マージソートの実装が完了です。
これで、配列を効率的にソートする方法が理解できたと思います。
まとめ
この記事では、C言語を用いて配列を降順でマージソートする方法について解説しました。
マージソートは、分割統治法を用いた効率的なソートアルゴリズムであり、安定ソートであるため、同じ値の要素の順序が保たれるという特徴があります。
完成したサンプルコードと実行結果
記事内で示したサンプルコードを実行することで、配列が正しく降順にソートされることを確認できます。
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] >= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int 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);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("初期配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
mergeSort(arr, 0, n - 1);
printf("ソート後の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}このコードを実行すると、以下のような出力が得られます。
初期配列: 38 27 43 3 9 82 10
ソート後の配列: 82 43 38 27 10 9 3マージソートは効率的で安定したソートアルゴリズムであり、C言語での実装も比較的シンプルです。
降順ソートを実現するためには、マージ関数内の比較演算子を適切に設定することが重要です。
今後のプログラミングに役立ててください。
