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[左] >= pivot_value
  3. A[右] <= pivot_value

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

这不是继续使用的正确分区。

于 2013-03-09T20:59:15.027 回答