よろしければ宿題のお手伝いをさせていただきます。基本的には、値の配列に対してクイックセレクトを実行するという考え方ですが、テンプレートが提供されており、提供されているもので関数を機能させる方法がわからないようです。
問題は、値が正しく配置されないか、配置されている場合、同じ値が入力されるたびに値が変更されることです。
これが私が使用している関数です。コードの後に/**/を使用して記述したコードを示し、他の行は私に提供されたテンプレートの一部です。
#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
これについての助けをいただければ幸いです。私の教授はこれがどのように機能するかをまったく説明していませんでした。オンラインで見つけた他の例は私の質問に答えません。私はこれを実装するさまざまな方法をいじくり回して何時間も費やしてきましたが、現時点ではまったくわかりません。ありがとう
編集:変更されたため、直接実装およびコンパイルできるようになりました。私が使用しているライブラリも追加しました