C言語のクイックソートを徹底解説！仕組み・手順・サンプルコード付き

ソート（整列）とは、データの要素を昇順または降順に並べ替える処理のことです。本記事では、C言語で利用できる代表的なソート手法のひとつであるクイックソートについて、その基本的な考え方から具体的な実装方法までを詳しく解説します。

C言語で使われる主なソートの種類

C言語では、主に以下の5つのソート手法が知られています。

• バブルソート（交換ソート）
• 選択ソート
• 挿入ソート（線形ソート）
• クイックソート（分割交換ソート）
• マージソート（外部ソート）

クイックソートとは

クイックソートは「分割統治法（divide and conquer）」に基づくアルゴリズムです。平均計算量が O(n log n) と高速なため、大量のデータを扱う場面で広く活用されています。

アルゴリズムの基本手順

1. ステップ1：配列から1つの要素を選び、それを「ピボット（基準値）」と呼びます。
2. ステップ2：未ソートの配列を2つの部分配列に分割します。
3. ステップ3：ピボットより小さい値を最初の部分配列へ、ピボットより大きい値を持つ残りの要素を2番目の部分配列へ振り分けます。

具体例による動作の確認

以下の例では、図中の記号を次のように定義しています。

• P：ピボット要素
• L：左ポインタ
• R：右ポインタ

対象となる要素は 6, 3, 7, 2, 4, 5 の6個です。

一連のポインタ操作が完了すると、配列は次のような状態になります。

• ピボットが確定位置に配置される
• 左側の要素はすべてピボットより小さい値になる
• 右側の要素はすべてピボットより大きい値になる
• ここで配列を「左側」「右側」の2つの部分配列に分割する
• 左側の部分配列に対して、同じくクイックソートを適用する

さらに同様の手順を再帰的に繰り返すことで、次の状態へと進みます。

• 各段階のピボットが確定位置に配置される
• 左側の要素は小さく、すでにソート済み
• 右側の要素も大きく、ソート済みの状態になっている
• 最終的に2つの部分配列を結合した結果として、2, 3, 4, 5, 6, 7 の整列済みリストが完成する

クイックソートのC言語サンプルプログラム

以下は、クイックソートの手法を使って要素を昇順に並べ替えるCプログラムの例です。

#include<stdio.h>
void quicksort(int number[25],int first,int last){
    int i, j, pivot, temp;
    if(first<last){
        pivot=first;
        i=first;
        j=last;
        while(i<j){
            while(number[i]<=number[pivot]&&i<last)
            i++;
            while(number[j]>number[pivot])
            j--;
            if(i<j){
                temp=number[i];
                number[i]=number[j];
                number[j]=temp;
            }
        }
        temp=number[pivot];
        number[pivot]=number[j];
        number[j]=temp;
        quicksort(number,first,j-1);
        quicksort(number,j+1,last);
    }
}
int main(){
    int i, count, number[25];
    printf("How many elements are u going to enter?: ");
    scanf("%d",&count);
    printf("Enter %d elements: ", count);
    for(i=0;i<count;i++)
    scanf("%d",&number[i]);
    quicksort(number,0,count-1);
    printf("Order of Sorted elements: ");
    for(i=0;i<count;i++)
    printf(" %d",number[i]);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

How many elements are u going to enter?: 10
Enter 10 elements: 2 3 5 7 1 9 3 8 0 4
Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9