2

ソート中の重要な操作の数をカウントする C++ クイックソート アルゴリズムに取り組んでいます。100 個の値を正しく並べ替えますが、その後は無限ループに陥ります。どんな助けでも大歓迎です！

//QuickSort.cpp

#include "QuickSort.h"
#include <algorithm>

using namespace std;

QuickSort::QuickSort(int max) : SortData(max)
{
    /*
    maxSize = max;
    theData = new long[max];
    */
    SortData::randomize(12);

}

QuickSort::~QuickSort(void)
{

}

_int64 QuickSort:: sort()
{
    numops = 0;
    quicksort(theData, 0, (size()-1));
    return(numops);
}

//Include counting number of operations
void QuickSort::quicksort(long theData[], int left, int right)
{
    //Default variables

    if (size() <= 1 || left >= size() || right >= size()) return; //Bounds checking

    if (left < right)
    {
        long pivot = partition(theData, left, right);

        quicksort(theData, left, pivot-1);
        quicksort(theData, pivot+1, right);
    }
}

int QuickSort::partition(long theData[], int left, int right)
{
    long pivot = theData[left];
    while (true)
    {
        while (theData[left] < pivot) left++;
        numops ++;

        while (theData[right] > pivot) right--;
        numops ++; 

        if (left < right)
        {
            swap(theData[left], theData[right]);
            numops+=3;
        }

        else
        {
            return right;
        }
    }
}

//QuickSort.h

#pragma once
#include "SortData.h"

class QuickSort : public SortData
{

public:
    QuickSort(int max = 100);
    ~QuickSort(void);
    _int64 sort();
private:
    _int64 numops;
    void QuickSort::quicksort(long theData[], int left, int right);
    int partition(long theData[], int left, int right);
};
4

2 に答える 2

4

パーティション関数では、

 if (left < right)

常に真実です。したがって、無限のwhile（true）ループが発生します。

また、SortData.hのsize（）関数に問題がある可能性がありますが、まだ確認できません。

データはランダムであるため、一部の入力セットで問題が発生することがあります。

わずかな変更が役立つはずです：

if (left <= right) {
         if (left < right) {
             swap(theData[left], theData[right]);
             numops += 3;
         }
         left++;
         right--;
}
else {
    return right;
}

再確認してすみません:)

于 2012-05-22T20:11:15.140 に答える
1

partitionと の場合にスタックleft < rightしtheData[left] == theData[right]ます。

于 2012-05-22T20:15:14.847 に答える