具有两个循环的分区算法C ++ [英] Partition algorithm with two loops c++

问题描述

为我提供了分区算法的伪代码，但我不确定如何实现。

I was given pseudo code for a partition algorithm but I'm not really sure how to implement it.

下面是伪代码和我的实现。请让我知道这是否正确/解释其工作方式。现在我对它有部分了解，但这是不正确的。

Below is the pseudo code and my implementation. Please let me know if this is correct/explain what it's doing. Right now I have a partial understanding of it but it is not correct.

输入：0.963、0.003、0.0251、0.353、0.667、0.838、0.335、0.915、0.796， 0.833、0.345、0.871、0.089、0.888、0.701、0.735

Input: 0.963, 0.003, 0.0251, 0.353, 0.667, 0.838, 0.335, 0.915, 0.796, 0.833, 0.345, 0.871, 0.089, 0.888, 0.701, 0.735

期望：0.003 0.0251 0.089 0.335 0.345 0.353 0.667 0.701 0.735 0.796 0.833 0.838 0.871 0.888 0.915 0.963

Expected: 0.003 0.0251 0.089 0.335 0.345 0.353 0.667 0.701 0.735 0.796 0.833 0.838 0.871 0.888 0.915 0.963

实际：0.003000 0.025100 0.353000 0.667000 0.838000 0.335000 0.915000 0.796000 0.833000 0.345000 0.871000 0.089000 0.888000 0.7 01000 0.735000 0.963000

Actual: 0.003000 0.025100 0.353000 0.667000 0.838000 0.335000 0.915000 0.796000 0.833000 0.345000 0.871000 0.089000 0.888000 0.7 01000 0.735000 0.963000

int partition_data( float xdata[], int ndata, float xmiddle ) {
  int left;
  int right;
  int j,i;
  float temp;

  for(i = 0; i < xmiddle; i ++){
    if(left == right){
      left += 1;
    }
    else{
      for( j = ndata - 1; j >= xmiddle; j--){
        if(left == right){
          right -= 1;
        }
        else{
          temp = xdata[j];
          xdata[j] = xdata[i];
          xdata[i] = temp;

          right -= 1;
          if(left == right){
            left += 1;
            break;
          }
        }
      }
    }
  }

}

推荐答案

正如其他人已经说过的，无论是在此处还是在Code Review上，伪代码都是非标准的，而且很难阅读（尽管它是

As others already said, both here and at Code Review, the pseudocode is quite non-standard, and hard to read (although it's not true it is mis-indented).

但是，如果您对改进它不感兴趣，而只是想按原样实施，就可以了。 ，逐字翻译成C语言：

However, if you're not interested in improving it, but just want to implement it 'as is', here it is, word-by-word translated into C language:

int Partition(float X[], int ndata, float xmiddle)
{
    int left  = 0;
    int right = ndata - 1;
    while(1) {              // 'left' loop
        if(X[left] < xmiddle)
        {
            if(left == right)
                return left + 1;
            left ++;
        }
        else
            while(1) {     // 'right' loop
                if(X[right] >= xmiddle)
                {
                    if(left == right)
                        return left;
                    right --;
                }
                else
                {
                    float tmp = X[left];    // these three lines
                    X[left] = X[right];     // swap the two values
                    X[right] = tmp;         // X[left] and X[right]

                    right --;
                    if(left == right)
                        return left + 1;
                    left ++;
                    break;           // exit the 'right' loop
                }
            }     // end of 'right' loop
    }   // end of 'left' loop
} // end of Parition

代码实际上是C，在C ++中，您可以使其成为带有类型参数的函数模板，而不是显式的 float ，以便函数可以对不同类型的数组进行分区（只要运算符< 和> = 定义）。您也可以使用 std :: swap 进行有效的数据交换，并删除显式的 tmp 变量。

The code is actually C, in C++ you might make it a function template with a type parameter instead of explicit float, so that the function may partition arrays of different types (as long as operators < and >= are defined). You might also use std::swap for efficient swapping data and dropping the explicit tmp variable.

这篇关于具有两个循环的分区算法C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！