-1

こんにちは、サイズが 2500 から 25000 の間で配列をソートするときに、いくつかのソート アルゴリズムのパフォーマンスをテストしています。比較している 2 つのソートは、Gnome ソートとクイック ソートです。はるかに高速ですが、Gnome の並べ替えはすべての場合に勝っています。

QuickSort のコードは次のとおりです。

void myQuickSort(Record sRecord[], int firstElement, int lastElement, bool (*funPoint)   (int,int))
{
int i = firstElement;
int j = lastElement;
int temp;
char tmpname[NAMESIZE];


int pivot = sRecord[(firstElement + lastElement) / 2].score;

bool (*myPoint)(int,int) = funPoint;

while (i <= j)
{
    while (sRecord[i].score < pivot)
    {
        i++;
    }
    while (sRecord[j].score > pivot)
    {
        j--;
    }

    if(compareResult(sRecord[j].score,sRecord[i].score) == false)
    {
        temp = sRecord[i].score;
        strcpy(tmpname,sRecord[i].name);

        sRecord[i].score = sRecord[j].score;
        strcpy(sRecord[i].name,sRecord[j].name);

        sRecord[j].score = temp;
        strcpy(sRecord[j].name, tmpname);

        i++;
        j--;
    }

    if(firstElement < j)
    {
        myQuickSort(sRecord, firstElement, j, compareResult);
    }
    if(i < lastElement)
    {
        myQuickSort(sRecord, i, lastElement , compareResult);
    }
}
}

GnomeSort は次のとおりです。

void myGnomeSort(Record sRecord[], int size, bool (*funPoint)(int,int))
{
     int pos = size, temp;
     char tmpname[NAMESIZE];

     bool (*myPoint)(int,int) = funPoint;

     while(pos > 0)

     {

         if (pos == size || myPoint(sRecord[pos].score, sRecord[pos-1].score) == false)

             pos--;

         else
         {
             temp = sRecord[pos].score;
             strcpy(tmpname,sRecord[pos].name);

             sRecord[pos].score = sRecord[pos-1].score;
             strcpy(sRecord[pos].name,sRecord[pos-1].name);

             sRecord[pos-1].score = temp;
             strcpy(sRecord[pos-1].name, tmpname);

             pos--;

          }
     }  
}

クイックソート (2.5k とほぼ 5 倍の長さの要素) を使用すると、なぜ劇的な増加があるのか​​ について、誰かが光を当てることができますか?

手伝ってくれてありがとう

編集：テストに使用されるコードは

Record smallRecord[25000];
populateArray(smallRecord, 25000);

int startTime = GetTickCount();

for(int times = 0; times < NUMOFTIMES; times++)
{
    populateArray(smallRecord, 25000);
    myGnomeSort(smallRecord, 25000, compareResult);
    cout << times << endl;
}

int endTime = GetTickCount();
float timeMS = ((float) (endTime - startTime)) / 1000;

cout << "Time taken: " << timeMS << endl;

populate array 関数は、配列に乱数を入力するだけです。

4

1 に答える 1

-1

実際、クイックソートの複雑さはO(N^2)であり、最悪の場合ではなく、平均でO(N * logN)です。O(N^2)で機能するデータが常に存在するため、クイックソートの使用はお勧めしません。

于 2013-03-24T20:33:37.237 に答える