多数の要素でクイックソートを実行するC++プログラム

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

ここでは、ソートする大きな配列（ほぼ100個の要素）を検討しています。いくつかの番号を取得し、ランダム化された順序でシャッフルして、並べ替えられないようにします。次に、クイックソート手法を使用して並べ替えます。

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

• 時間計算量 − 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
   pivot := array[upper]
   i := lower – 1
   for j in range lower to higher, do
      if array[j] < pivot, then
         exchange the values of array[i] and array[j]
         i := i + 1
   done
   exchange the values of array[upper] and array[i + 1]
   return i + 1
End

quickSort（配列、左、右）

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

出力 −ソートされた配列

Begin
   if lower < right then
   q = 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;
   }
}
int partion(int arr[], int p, int r) {
   int pivot = arr[r]; //last item as pivot
   int i = p - 1;
   for (int j = p; j < r; j++) {
      if (arr[j] < pivot) {
         i++;
         swap(arr[i], arr[j]);
      }
   }
   swap(arr[i+1], arr[r]);
   return i + 1;
}
void quick_sort(int arr[], int p, int q) { //recursively sort the list
   int j;
   if (p < q) {
      j = partion(arr, p, q);
      quick_sort(arr, p, j - 1);
      quick_sort(arr, j + 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