0

に基づいて Qsort を使用していemployee.lastnameます。
left通過した回数のカウンターです。
emptotal, (またはright) は合計何個あるかです。
私は 5 つあることを知っているので、ピボット ポイントを 3 に強制しました。カウントアップ (またはカウントダウン) してから、エンドカウンターに到達する必要があります。

#include "./record.h"
#include <string.h>
#include <algorithm>

void externalSort(EmployeeRecord employee[],int empcount,int emptotal)
{
    int left=empcount,
        right=emptotal;    
    EmployeeRecord pivot = employee[3];    
    while (left < right) 
    {
        if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
        {    
            left++; 
        }
        else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
        {
            right--; 
        }
        else 
        {
            std::swap(employee[left],employee[right]);
            left++;
            right--;
        }
    }

    if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
    {
        std::swap(employee[left],employee[empcount]);
        left--;
    }
    if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
    {
        std::swap(employee[right],employee[empcount]);
        right++;
    }

    if (empcount < right) externalSort(employee,empcount,right);
    if (left < emptotal) externalSort(employee,left,emptotal);
// The 2nd call is what seems to be looping, when I comment it out, 
    //the function doesn't loop.

}
4

2 に答える 2

1

employee[3]並べ替える必要があるものの数に関係なく、3 番目のものではなく 4 番目のものを選択します。

ループ

while (left < right)

チェックするように指示した項目をチェックしますが、ピボットはその範囲にない可能性があります。

それに対処する方法を決定した後、さらに3つの間違い/考えるべきことがあります.

  1. 最後のブランチでスワップする必要がありますか?
  2. 再帰するときは、externalSort(employee,empcount,pivot_index-1) を試してください
  3. externalSort(employee,left, emptotal) と同様に、ピボット インデックス + 1 を使用する必要があります

Wikipediaには、比較的明確な疑似コードがいくつかあります。毎回 3 番目のポイントを使用できると想定しました。再帰すると、3 つ未満になる場合があります。

于 2013-07-29T17:39:03.567 に答える
0

私が最初に行うことは、strcmp ステートメントが実際に実行されていることを確認することです。

if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
{    
left++; 
}
else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
{
right--; 
}

左のステートメントは正しいと思いますが、右のインデックスの姓がピボットよりも小さいかどうかを確認していますが、おそらくそれが大きいかどうかを確認する必要があります。多くの場合、このような小さなことで予期しないコード フローが発生します。ただし、これですべてが解決するとは思いません。

于 2013-07-29T17:51:24.687 に答える