QuickSort用のC++プログラム？

クイックソートは、比較を使用してソートされていないリスト（配列）をソートするソート手法です。クイックソートは、パーティション交換ソートとも呼ばれます。

等しいソート項目の相対的な順序が保持されないため、安定したソートではありません。クイックソートは配列を操作できるため、ソートを実行するために少量の追加メモリが必要です。常に最悪の場合のパーティションを選択するわけではないことを除いて、選択ソートと非常によく似ています。したがって、選択ソートのより適切な形式と見なすことができます。

QuickSortは、最も効率的な並べ替えアルゴリズムの1つであり、配列を小さい配列に分割することに基づいています。この名前は、クイックソートが一般的な並べ替えアルゴリズムのどれよりも大幅に高速にデータ要素のリストを並べ替えることができるという事実に由来しています。マージソートと同様に、クイックソートも問題解決方法論の分割統治アプローチのカテゴリに分類されます。

クイックソートアルゴリズムは次のように機能します

• 類推的な見方をして、生徒の名前が書かれた論文を名前で並べ替えなければならない状況を考えてみましょう。次のようなアプローチを使用できます-

  • 分割値、たとえばLを選択します。分割値はピボットとも呼ばれます。

  • 紙の束を2つに分けます。 A-LおよびM-Z。杭が同じである必要はありません。

  • A-Lパイルで上記の2つの手順を繰り返し、重要な2つの半分に分割します。そして、M-Zパイルは半分に分割されます。パイルが簡単に分類できるほど小さくなるまで、このプロセスが繰り返されます。

  • 最終的には、小さい山を積み重ねて、完全に分類され、順序付けられた一連の紙を作成できます。

• ここで使用されるアプローチは再帰です 単一要素配列に到達するために各分割で。

• 分割するたびに、杭が分割され、小さい杭にも同じアプローチが使用されました。

• これらの機能により、クイックソートはパーティション交換ソートとも呼ばれます。 。

Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7

説明

概念を理解するには、例が役立つ場合があります。次の配列について考えてみます：50、23、9、18、61、32

ステップ1 −リストからピボットとなる値（通常は最後の値）を決定します。最初のインデックスと最後のインデックスに対応する2つの値「Low」と「High」があるとします。

この場合、lowは0で、highは5です。

低値と高値は50と32で、ピボットの値は32です。

したがって、ピボット（32）が実際の位置になるようにアレイを再配置して、パーティションを作成する必要があります。そして、ピボットの左側には、配列のすべての要素がそれよりも小さく、右側にはそれよりも大きくなっています。

分配関数では、最初の要素から始めて、それをピボットと比較します。 50は32より大きいため、変更を加えずに次の要素23に進みます。

ピボットともう一度比較してください。 23は32未満なので、50と23を入れ替えます。配列は23、50、9、18、61、32になります。

次の要素9に移動します。これもピボット（32）未満であるため、50と交換すると、配列は次のようになります。

23、9、50、18、61、32。

同様に、32未満の次の要素18の場合、配列は次のようになります

23、9、18、50、61、32これで、61はピボット（32）よりも大きくなるため、変更はありません。

最後に、ピボットを50に交換して、正しい位置に配置します。

したがって、ピボット（32）は実際の位置にあり、左側のすべての要素は小さく、右側のすべての要素はそれ自体よりも大きくなっています。

ステップ2 −したがって、最初のステップの後の配列は次のようになります

23、9、18、32、61、50、32をピボットとして使用します。

ステップ3 −現在、リストは2つの部分に分かれています：

1.ピボット前のサブリスト：23、9、18

2.ピボット後のサブリスト：61、50

ステップ4 −これらのサブリストに対して手順をもう一度繰り返します。

したがって、最終的な配列は9、18、23、32、50、61になります。

例

#include <stdio.h>
void swap(int *a, int *b) {
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}
int Partition(int a[], int low, int high) {
   int pivot, index, i;
   index = low;
   pivot = high;
   for(i=low; i < high; i++) {
      if(a[i] < a[pivot]) {
         swap(&a[i], &a[index]);
         index++;
      }
   }
   swap(&a[pivot], &a[index]);
   return index;
}
int RandomPivotPartition(int a[], int low, int high) {
   int pvt, n, temp;
   n = rand();
   pvt = low + n%(high-low+1);
   swap(&a[high], &a[pvt]);
   return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high) {
   return 0;
}
int main() {
   int n, i;
   n=7;
   int arr[]={7,4,2,6,3,1,5};
   int high = n-1;
   int low = 0 ;
   int pindex;
   if(low < high) {
      pindex = RandomPivotPartition(arr, low, high);
      QuickSort(arr, low, pindex-1);
      QuickSort(arr, pindex+1, high);
   }
   for (i = 0; i < n; i++)
      printf("%d ", arr[i]);
   return 0;
}