6

これは、クイックソートアルゴリズムの実装に出くわしたコードです。ここで再帰がどのように機能するか説明していただけますか？

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

  /* partition */
  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--;
    }
}
/* recursion */
if (left < j)
    quickSort(arr, left, j);
if (i < right)
        quickSort(arr, i, right);
}

そして、これは宿題ではないことに注意してください。

4

3 に答える 3

8

「再帰がどのように機能しているかを説明する」とはどういう意味かわかりません。しかし、ここに行きます：

投稿した関数は、intの配列と2つのインデックスを取ります。配列全体をソートするのではなく、2つのインデックスの間の一部のみをソートし、それらの外側にあるものはすべて無視します。つまり、最初と最後のインデックスを渡した場合は同じ関数で配列全体を並べ替えることができ、配列の最初の要素のインデックスではない値leftや、right最後の要素のインデックス。

ソートアルゴリズムはよく知られているクイックソートです。ピボットとして、中央の要素を使用します（他の要素を使用することもできます）。less than (or equal to) pivot配列をサブ配列とサブ配列に分割しgreater than (or equal to) pivot、2つのパーティション間のピボットに等しい要素を残します。

次に、それ自体を再帰的に呼び出して2つのパーティションをソートしますが、必要な場合にのみそれを実行します（したがって、再帰呼び出しの前にifsを呼び出します）。

実装は機能しますが、多くの点で最適ではなく、改善される可能性があります。考えられる改善点は次のとおりです。

  1. 配列が十分に短い場合は、別の並べ替えアルゴリズムに切り替えます
  2. 3つの値の中央値としてピボット値を選択しました（通常、最初、最後、および中央値）
  3. 最初に1つのピボット値を配列から移動し（最初または最後の位置に配置し、配列の残りの部分にフォーカスを減らします）、次に、ピボットに等しい値を渡すようにテストを変更して、それらに関連するスワップの数を減らします。最後に最終交換を行って、ピボット値を元に戻します。これは、提案2に従わず、この実装のように中間要素ではなく、最初/最後の要素を選択した場合に特に役立ちます。
于 2012-08-15T19:06:47.250 に答える
4

返信が遅れましたが、プリントをいくつか追加しただけで、これに出くわした人は誰でもコードを理解するのに役立つかもしれません。

#include<iostream>
using namespace std;

void quickSort(int arr[], int left, int right)
 {
  int i = left, j = right;
  int tmp;
  int pivot = arr[abs((left + right) / 2)];
  cout<<"pivot is"<<pivot<<endl;

  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl;
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
              cout<<"entering first big while loop"<<endl;
         for(int i=0;i<7;i++)
    cout<<arr[i]<<" "<<endl ;
    }
}
cout<<"recursion"<<endl;

/* recursion */
if (left < j)
    quickSort(arr, left, j);

if (i< right)
        quickSort(arr, i, right);
}
int main(){
    int arr[7]= {2,3,8,7,4,9,1};
        for(int i=0;i<7;i++)
    cout<<arr[i]<<" " ;
    quickSort(arr,0,6);
    cout<<endl;
    for(int i=0;i<7;i++)
    cout<<arr[i]<<" " ;
int wait;
cin>>wait;
return 0;
}
于 2012-11-26T09:23:22.357 に答える
1

これがあなたの答えです-一般的なケースでは、上記の条件が真になるため、両方の再帰呼び出しが実行されます。ただし、コーナーケースでは、ピボット要素を最大（または最小）の要素にすることができます。この場合、再帰呼び出しを1回だけ行う必要があります。これにより、基本的に、配列からピボット要素を削除した後に別のピボットを選択して、プロセスをもう一度試行します。

于 2012-08-15T18:52:48.120 に答える