ランダム化を使用してクイックソートを実装するC++プログラム

クイックソート手法は、リストを2つの部分に分割することによって行われます。最初に、ピボット要素は分割アルゴリズムによって選択されます。ピボットの左側の部分はピボットよりも小さい値を保持し、右側の部分は大きい値を保持します。分割後、それぞれの個別のリストは同じ手順を使用して分割されます。

この場合、ピボット要素をランダムに選択しています。ピボットを選択した後、パーティショニングを実行し、配列を再帰的に並べ替えます。

クイックソート手法の複雑さ

• 時間計算量 − O（n log n）は、最良の場合と平均的な場合、O（n ² ）最悪の場合。

• スペースの複雑さ − o（log n）

入力 −ソートされていないリスト：90 45 22 11 22 50
出力 −並べ替え後の配列：11 22 22 45 50 90

アルゴリズム

partition（array、lower、upper）

入力 −データセット配列、下限と上限

出力 −正しい位置でピボット

Begin
   index := lower
   pivot := higher
   for i in range lower to higher, do
      if array[i] < array[pivot], then
         exchange the values of array[i] and array[index]
         index := index + 1
   done
   exchange the values of array[pivot] and array[index]
End

random_pivot_partition（array、lower、upper）

入力 −データセット配列、下限と上限

出力 −ランダムに選択されたピボットの最終インデックス

Begin
   n := a random number
   pvt := lower + n mod (upper – lower + 1)
   exchange the values of array[pivot] and array[upper]
   index := Partition(array, lower, upper)
   return index
End

quickSort（配列、左、右）

入力 −データの配列、および配列の下限と上限

出力 −ソートされた配列

Begin
   if lower < right then
      q = random_pivot_partition(array, left, right).
      quickSort(array, left, q-1)
      quickSort(array, q+1, right)
End

サンプルコード

#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) {
   //function to shuffle the array elements into random positions
   srand(time(NULL));
   for (int i = MAX - 1; i > 0; i--) {
      int j = rand()%(i + 1);
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high) {
   int pivot, index, i;
   index = low;
   pivot = high;
   for(i=low; i < high; i++) {
      // finding index of pivot.
      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){
   // Random selection of pivot.
   int pvt, n, temp;
   n = rand();
   pvt = low + n%(high-low+1); // Randomizing the pivot value from sub-array.
   swap(a[high], a[pvt]);
   return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
   //recursively sort the list
   int pindex;
   if(p < q) {
      pindex = RandomPivotPartition(arr, p, q); //randomly choose pivot
      // Recursively implementing QuickSort.
      quick_sort(arr, p, pindex-1);
    quick_sort(arr, pindex+1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX; i++)
arr[i] = i + 1;
random_shuffle(arr); //To randomize the array
quick_sort(arr, 0, MAX - 1); //sort the elements of array
for (i = 0; i < MAX; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}

出力

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100