マージソート
安定ソートです。
「マージソート」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
安定ソート
Mergesortは、配列を半分に分割し、それぞれをソートしてからマージする分割統治法によるソートです。どの場合でも計算量はO(n log n)で、安定です。
分割ステップ
配列を中央で再帰的に分割し、各部分が1要素になるまで続けます。1要素の配列は自明にソート済みであり、これがベースケースです。
マージステップ
中心となる処理は、すでにソートされた2つのランを1つにマージすることです。両方をインデックスポインタで走査し、先頭にある小さい方の要素を常に次へコピーします。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}安定である理由
マージではa[i] <= a[j]を使うため、2つの要素が等しい場合は左のランの要素を先に選びます。左のランには先に現れた要素が入っているため、元の順序が保たれます。
再帰処理
Mergesortはそれぞれの半分に対して再帰し、その後でマージします。呼び出しごとのメモリ割り当てを避けるため、共有スクラッチバッファを渡します。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}メモリ使用量
quicksortとは異なり、mergesortではマージ用バッファとしてO(n)の追加メモリが必要です。メモリに余裕がない環境で非常に大きな配列を扱う場合、これが主な欠点になります。
保証されたO(n log n)
再帰では常に半分に分割するため、レベル数はlog nになります。また、各レベルではn個の要素をマージします。そのため、quicksortとは異なり、mergesortは最良、平均、最悪のすべての場合でO(n log n)です。
マージレベルの計算
再帰レベルの数はceil(log2 n)です。いくつかのサイズについて計算してみましょう。
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}ボトムアップmergesort
反復処理による変種で、サイズ1、次に2、次に4のランをマージし、各パスでサイズを2倍にします。再帰を完全に避けられ、連結リストにも適しています。
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Mergesortを選ぶ場面
次の条件が必要な場合は、mergesortを優先してください。
- 悪いケースのない、保証されたO(n log n)
- 安定性
- 連結リストのソート（ランダムアクセスが不要）
- RAMに収まらない大きさのデータの外部ソート
MergesortとQuicksortの比較
Quicksortは通常、実際の処理ではより高速で、インプレースでソートできますが、最悪ケースでは不安定です。Mergesortは安定しており計算量が保証される一方、追加メモリを使用します。制約に応じて選択してください。
理解度チェック
mergesortについての理解度を確認しましょう。
まとめ
mergesortについて学びました。
- 半分に分割し、それぞれをソートしてからマージする
- マージでは等しいキーの場合に左側を先にするため、安定性が得られる
- すべての場合でO(n log n)が保証される
- O(n)の追加メモリを使用するが、連結リストや外部ソートに適している
よくある質問
「マージソート」レッスンは無料ですか？
はい。「マージソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「マージソート」で何を学びますか？
安定ソートです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「マージソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。