2

複数の条件でクイックソートをソートする方法はありますか? たとえば、エッジのセットがあります。各エッジには、ソース、宛先、および長さがあります。最初に長さの短いエッジを配列に入れたいと思います。しかし、長さが同じ場合は、元の頂点が小さいもので並べ替えたいと思います。これらのソース頂点が同じ場合、2 つの宛先頂点のうち小さい方で並べ替えたいと思います。

例えば：

4 (ソース) 2 (宛先) 3 (長さ)

1 (ソース) 5 (宛先) 3 (長さ)

どちらも同じ長さなので、ソース頂点を見ます。2 番目のエッジは最初のエッジよりも小さいため、ソース頂点で比較するため、それらを交換します。

以下は私のクイックソートで、なぜ正しくソートされないのか正直わかりません.クイックソートの効率を下げて安定させる方法があれば、喜んで提案します!

void quickSort(edge *e, int left, int right)
{
  int i = left, j = right;
  int temp, temp1, temp2;
  int pivot = (left + right)/2;
  while(i <= j)
  {
    while(e[i] < e[pivot])
      i++;
    while(e[pivot] < e[j])
      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);
}

私の条件の並べ替え：

bool edge::operator<(const edge &other) const 
{
    if (length < other.length)
        return true;
     else if ((length == other.length) && (source < other.source))
        return true;
     else if((length == other.length) && (source == other.source) && (destination < other.destination))
        return true;
     return false;
}

繰り返しになりますが、このクイックソートの時間の複雑さを減らして安定させることで、このクイックソートを正しく行う方法を誰かが知っている場合は、喜んで提案を受け付けます! ありがとうございました！何か助けはありますか？

編集：これが私のクイックソートを呼び出す方法です。読み取ったエッジの数に基づいて呼び出しました。

    quickSort(e, 0, edges-1); //-1 because if you put in edges, it'd go past the bounds of the array

編集:アルゴリズムに次のようなものを入れようとすると:

0 1 1

0 3 1

1 3 1

2 5 1

4 10 1

4 8 1

10 8 1

11 6 2

11 7 2

6 7 1

9 6 1

9 7 1

これは出力です：

0 1 1

0 3 1

1 3 1

2 5 1

4 8 1

4 10 1

6 7 1

6 9 1

8 10 1 <- 7 9 1 未満であること

7 9 1 <- 8 10 1 を超える必要があります

6 11 2

7 11 2

4

2 に答える 2

1

このように書いた方がきれいです

if (length != other.length)
   return length<other.length;

if ( source != other.source)
   return source < other.source;

return destination < other.destination;

temp = e[i]メンバーはすべてintであるため、などもできるはずです。

これ（および提出したコード）は、あなたが望むタスクを実行するはずです。

安定性の問題がある場合、それはクイックソートが安定していないためです。lhs==rhsそれが起こらないように、条件を追加することで回避できます。または、 Mergesortを試すことができます

率直に言って、クイックソートの経験はあまりありませんが、あなたの実装はWikipedias In Place Algorithmとは著しく異なって見えます。たとえば、ピボットはまったく移動しません。それが問題かどうか確認していただけますか？

編集

あなたのリンクを見た後

リンクされたアルゴリズムも、ピボットをインデックスとしてではなく値として使用しているようです(あなたがそうしているように)。ピボット値が移動する可能性があると考えるまでは、構文的には同じように見えます。その後、ピボット インデックスは別のものを指します。

int pivot = arr[(left + right) / 2];

これは役に立ちますか？

于 2012-11-19T01:19:30.507 に答える