0

よろしければ宿題のお手伝いをさせていただきます。基本的には、値の配列に対してクイックセレクトを実行するという考え方ですが、テンプレートが提供されており、提供されているもので関数を機能させる方法がわからないようです。

問題は、値が正しく配置されないか、配置されている場合、同じ値が入力されるたびに値が変更されることです。

これが私が使用している関数です。コードの後に​​/**/を使用して記述したコードを示し、他の行は私に提供されたテンプレートの一部です。

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int partition(int *A, int len, int pivot_index)
{
   int pivot_value = A[pivot_index]; /**/

   int left = 0; /**/
   int l = left; /**/
   int right = len - 1; /**/
   while(left < right)  /**/
   { /**/
      while(A[left] < pivot_value) /**/
      { /**/
         left++; /**/
      } /**/

      while(A[right] > pivot_value) /**/
      { /**/
         right--; /**/
      } /**/

      if(A[left] < pivot_value) /**/
      { /**/
         swap(A[left], A[right]); /**/
      } /**/
  } /**/

  return left; /**/
}


int select (int *A, int len, int rank)
{
      if (len==1) return A[0];
      int pivot_index = rand() % len;
      int pivot_rank = partition(A, len, pivot_index);  

      if (rank == pivot_rank) return A[rank];
      if (rank < pivot_rank) return select(A, pivot_rank, rank);
      return select(A, len - pivot_rank, rank - pivot_rank ); /**/
}

int main(void)
{
   int N, *A;

   ifstream fin("test.txt");
   fin >> N;
   A = new int[N];
   for (int i=0; i<N; i++) fin >> A[i];
   fin.close();

   int r;
   cout << "Enter rank (0.." << N-1 << ")\n";
   while (cin >> r) {
      if (r < 0 || r >= N)
        cout << "Invalid rank\n";
     else 
        cout << "The element of rank " << r << " is " << select(A,N,r) << "\n";
   }

  delete[] A;
}

「test.txt」ファイルには次の値が含まれています。

10 -- this denotes the length of the array or how many values it will read in
7
14
12
2
25
18
15
13
100
63

これについての助けをいただければ幸いです。私の教授はこれがどのように機能するかをまったく説明していませんでした。オンラインで見つけた他の例は私の質問に答えません。私はこれを実装するさまざまな方法をいじくり回して何時間も費やしてきましたが、現時点ではまったくわかりません。ありがとう

編集:変更されたため、直接実装およびコンパイルできるようになりました。私が使用しているライブラリも追加しました

4

1 に答える 1

1

コードには多くの問題があります。

while(A[left] < pivot_value) {  left++; }

これは、左側が配列の末尾を超えていないことをチェックしません。

while(A[right] > pivot_value) { right--;} 

これは、配列の開始前に実行されないことを確認しません。

while(left < right) 

これが無限ループのとき

  1. 左 < 右
  2. A[左] >= ピボット値
  3. A[右] <= ピボット値

select(A, len - pivot_rank, rank - pivot_rank );

これは続行するのに適切なパーティションではありません。

于 2013-03-09T20:59:15.027 に答える