クイックソート
分割統治です。
「クイックソート」はCoddyKit上の無料C Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
分割統治
クイックソートは分割統治法によるソートです。ピボットを選び、より小さい要素を左に、より大きい要素を右に配置するよう配列を分割してから、それぞれの部分を再帰的にソートします。
平均計算量は O(n log n) です。
分割の手順
重要な考え方は分割です。ピボットを基準に配列を並べ替え、ピボットの左側をすべて小さく、右側をすべて大きくします。すると、ピボットはソート後の最終位置に置かれます。
Lomuto分割法
Lomuto法では、最後の要素をピボットに使います。小さい要素の境界を示すインデックスiを保持し、走査しながら交換します。
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}再帰的なソート
クイックソートは分割を実行し、ピボットの両側にある2つの部分配列に対して再帰します。部分配列のサイズが0または1になったら、再帰を終了します。
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}適切なピボットの選択
ピボットが不適切だと（たとえば整列済みの入力で常に最後の要素を選ぶと）、計算量が O(n²) になります。よりよい選択をすると、分割をより均等にできます。
- 中央値の中央値（median-of-three）
- ランダムなピボット
中央値の中央値
中央値の中央値では、最初・中央・最後の要素の中央値をピボットに選び、整列済みデータで最悪の動作になることを避けます。
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}最悪計算量の分析
各分割で要素が1つだけ切り離されると、再帰の深さは n になり、計算量は O(n²) になります。これは、整列済みまたは逆順に整列された入力に対して固定のピボットを使うと発生します。
ランダム化により、最悪のケースが発生する可能性を大幅に下げられます。
ランダムなピボット
分割する前にランダムな要素をピボット位置へ交換しておくと、悪意のある入力に対しても耐性を持たせられます。
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}インプレースで不安定
クイックソートは、平均で O(log n) のスタック領域だけを使ってインプレースにソートします。ただし安定ではありません。分割時の交換によって、等しい要素の順序が入れ替わる場合があります。
末尾再帰の最適化
小さい側を先に再帰的に処理し、大きい側をループで処理すると、スタックの深さを O(log n) に抑えられます。これにより、大きな配列でのスタックオーバーフローを防げます。
文字列のソート
同じ構造で、比較可能な任意の型をソートできます。ここではクイックソートで整数の配列を並べ替えていますが、比較処理を変更すれば他の型にも対応できます。
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}確認問題
クイックソートについての理解を確認しましょう。
まとめ
クイックソートを学びました。
- ピボットを基準に分割し、それぞれの側を再帰的に処理します
- 平均計算量は O(n log n)、最悪計算量は O(n²) です
- 中央値の中央値やランダムなピボットで最悪のケースを避けられます
- インプレースですが、安定ではありません
よくある質問
「クイックソート」レッスンは無料ですか？
はい。「クイックソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「クイックソート」で何を学びますか？
分割統治です。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「クイックソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- バブルソートと挿入ソート
- クイックソート
- マージソート
- qsort の利用