C言語でのクイックソート手法を説明します。

並べ替えは、要素を昇順（または）降順で並べ替えるプロセスです。

並べ替えの種類

C言語には、次の5つの並べ替え手法があります-

• バブルソート（または）Exchangeソート
• 選択ソート
• 挿入ソート（または）線形ソート
• クイックソート（または）パーティション交換ソート
• マージソート（または）外部ソート

クイックソート

これは分割統治アルゴリズムです。

• ステップ1-配列から要素を選択し、ピボット要素と呼びます。
• ステップ2-ソートされていない配列要素を2つの配列に分割します。
• ステップ3-ピボット要素よりも小さい値が最初のサブ配列に含まれる場合、ピボットよりも大きい値を持つ残りの要素は2番目のサブ配列に含まれます。

以下に示す例を考えてみましょう。

• Pはピボット要素です。
• Lは左ポインタです。
• Rは正しいポインタです。

要素は6、3、7、2、4、5です。

さて、

• ピボットは固定位置にあります。
• 左側の要素はすべて少なくなります。
• 適切な要素はピボットよりも優れています。
• 次に、アレイを左側と右側の2つのサブアレイに分割します。
• 左側のパーティションを取得してクイックソートを適用します。

さて、

• ピボットは固定位置にあります。
• 左側の要素はすべて少なく、並べ替えられています
• 適切な要素はより大きく、並べ替えられた順序になっています。
• 最終的にソートされたリストは、2つのサブ配列を組み合わせたものです2、3、4、5、6、7

例

以下は、クイックソート手法を使用して要素をソートする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