如果你不介意,我有一点功课帮助。基本上这个想法是对一组值执行快速选择,但是我们得到了一个模板,我似乎无法弄清楚如何让这些函数与所提供的内容一起工作。
问题是这些值不会正确排列,或者如果它们排列正确,它们会在每次输入相同的值时发生变化。
这是我正在使用的函数,我将在代码之后用 /**/ 表示我编写的代码,任何其他行都是为我提供的模板的一部分。
#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
对此的任何帮助将不胜感激。我的教授根本没有解释这将如何工作,我在网上找到的任何其他示例都不能回答我的问题。我花了很多时间摆弄不同的实现方式,此时我只是不知道。谢谢
编辑:更改,现在可以直接实现和编译。还添加了我正在使用的库