1

ソース頂点、デスティネーション頂点、長さの 3 つの変数を持つオブジェクトがあります。オブジェクトを長さでソートするクイックソートアルゴリズムがあります。ただし、2 つのオブジェクトを比較してそれらの長さが等しい場合、クイックソートで、ソース頂点が大きいオブジェクトの前にソース頂点が小さいオブジェクトが並べ替えられるようにしたいと考えています。それらも等しい場合は、宛先頂点を比較したいと思います。その前にある大きな宛先頂点を小さなソース頂点で並べ替えたいと思います。これはすべて配列で行われます。以下は私のクイックソートの実装です。e[i] は、頂点と長さを保持するオブジェクトであることに注意してください。

void quickSort(edge *e, int left, int right)
{
  int i = left, j = right;
  int temp, temp1, temp2;
  while(i <= j)
  {
    while(e[i].getLength() < pivot)
      i++;
    while(e[j].getLength() > pivot)
      j--;
    if(i <= j)
    {
      temp = e[i].getLength();
      temp1 = e[i].getEdgeSrc();
      temp2 = e[i].getEdgeDes();
      e[i].setLength(e[j].getLength());
      e[i].setEdgeSrc(e[j].getEdgeSrc());
      e[i].setEdgeDes(e[j].getEdgeDes());
      e[j].setLength(temp);
      e[j].setEdgeSrc(temp1);
      e[j].setEdgeDes(temp2);
      i++;
      j--;
    } //if statement
  }///while loop
  if(left < j)
    quickSort(e, left, j);
  if(i < right)
    quickSort(e, i, right);

}

長さが等しい場合、頂点のソートを実行する方法/場所を誰かが知っているでしょうか? ありがとう！

4

2 に答える 2

2

edge必要なことを実行するオブジェクトの比較演算子を定義するのが最適です。

class edge
{
  /* ... */
public:

  bool operator<(const edge &other) const
  {
     /* Length is first criterion: */
     if (length < other.length)
        return true;
     /* Source vertex is second criterion: */
     else if ((length == other.length) && (src < other.src))
        return true;
     return false;
  }

  /* ... */
};

次に、クイックソートの実装内で、etcに直接edgeアクセスするのではなく、この演算子を使用してオブジェクトを比較します。getLength()

while(e[i].getLength() < pivot)
  i++;

になります

while(e[i] < pivot)
  i++;

と

while(e[j].getLength() > pivot)
  j--;

になります

while(pivot < e[j])
  j--;

定義operator<したのは、ではなくoperator>、だけなので、それだけを使用することをお勧めします。または、定義することもできますoperator>。

上記でpivotは、これが現在のピボット要素への参照であると想定していることに注意してください。それが実際に現在のピボットの整数インデックスである場合は、それをに置き換える必要がありますe[pivot]。

std::swap(e[i],e[j]);別注： getステートメントとsetステートメントおよび一時変数の長い（そしてエラーが発生しやすい）シーケンスの代わりに使用することをお勧めします。

于 2012-11-13T07:15:38.680 に答える
0

長さを比較するのではなく、比較関数を作成して呼び出す必要があります。コードのどこにも定義していませんpivotが、によって返されるのと同じタイプだと思いますgetLength()。pivotインデックスになるように変更する必要があります。次に、次のように記述します。

while (compareEdge(e[i], e[pivot]) < 0)
    i++;
while (compareEdge(e[j], e[pivot]) > 0)
    j--;

関数compareEdgeは長さを比較します。それらが等しい場合は、説明したように頂点を比較します。

于 2012-11-13T07:16:12.083 に答える