java - クイックソートアルゴリズムの最悪のケースを生成する方法は?

Question

中央の要素をピボットとして考慮して、クイックソートの最悪のケースのセットを生成して出力するにはどうすればよいですか?. これは私のクイックソートアルゴリズムの実装です:

  void quickSort(int arr[], int left, int right) {

     int index = partition(arr, left, right);

        if (left < index - 1)

           quickSort(arr, left, index - 1);

        if (index < right)

           quickSort(arr, index, right);
 }


 int partition(int arr[], int left, int right){

  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

   while (i <= j) {
        while (arr[i] < pivot)
               i++; 
       while (arr[j] > pivot)

              j--;

        if (i <= j) {

              tmp = arr[i];

              arr[i] = arr[j];

              arr[j] = tmp;

              i++;

              j--;

        }

  };
  return i;

 }

このアルゴリズムの最悪のケースを生成する方法について何か考えはありますか?.

Answer 1

ピボット要素を最低または最高の数値に設定すると、最悪の場合が得られます。この場合の複雑さはO(n^2)です。

Answer 2

クイックソートの最悪のケースは、ピボットを配列内の最下位または最上位の要素として選択し、それを分割しようとした場合です。毎回、配列内の最下位または最上位の要素をパーティションとして選択し続けると、ほぼ n ^{2 回}の比較/スワップが行われます。この最悪のケースの動作を回避するには、線形時間 (O(n)) である中央値アルゴリズムの中央値を使用して適切なピボットを選択すると、最悪のケースが O(n log n) になります。