0

クイックソート用のクラスとオブジェクトを使用して、C++でプログラムを作成しました。これをオンライン コンパイラでコンパイルしたところ、このコードは時間とメモリを大量に消費するため、タイムアウトであることがわかりました。

後で Visual C++ 2010 でコンパイルしたunhandled exception : stack overflow ところ、クラス メンバー function で実行されている無限ループを把握しようとしていると表示されましたvoid quick sort (a[],l,r)。助けてください。

#include <iostream>
using namespace std;

class sort;

int main()
{
    class sort
    {
    public:
        int split(int a[],int l,int r)
        {
            int i,j,p,t;
            p=a[l];
            i=(l+1);
            j=r;

            while (l<=r)
            {
                while ((a[i]<p)&&(i<j))
                    r--;

                while ((a[j]>p)&&(l<r))
                    l++;

                if (i<=j)
                {
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            t=p;
            p=a[j];
            a[j]=p;

            return j;
        }


        void quicksort(int a[],int l,int r)
        {
            int s;
            if (l<r)
            {
                s=split(a,l,r);
                quicksort(a,l,(s-1));
                quicksort(a,(s+1),l);
            }
        }

    } obj1;

    int a[30],n,i;

    cout<<"\nEnter no of elements :\t 5";
    n=5;

    cout<<"\nEnter elements :\n";
    a[0]=9;
    a[1]=6;
    a[2]=3;
    a[3]=5;
    a[4]=1;

    cout<<"\nElemets before sort :\n";
    for(i=0;i<n;i++)
        cout<<" "<<a[i];

    obj1.quicksort(a,0,(n-1));

    cout<<"\nElements after sort:\n";
    for (i=0;i<n;i++)
        cout<<" "<<a[i];

    return 0;
}
4

1 に答える 1

2

ここにはいくつかの問題があります。

int split(int a[],int l,int r)
{
    int i,j,p,t;
    p=a[l];
    i=(l+1);
    j=r;

    // consider what will happen for an array with just 1 or 2 elements?
    while (l<=r) // should be while i<=j;
    {
        while ((a[i]<p)&&(i<j))
            r--; //should be j--

        while ((a[j]>p)&&(l<r))
            l++; // should be i++

        if (i<=j) // sadly this will only true when you've got an array with 1 element 
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    t=p;
    p=a[j];
    a[j]=p;

    return j;
}

ここで重要な問題は、クイックソート アルゴリズムが正しくないことです。次のように機能します。

0. make i = l+1 and j = r;

1. while true:

1.1 while a[i]<a[l] i++

1.2 while a[j]>a[l]  j--

1.3 break if i>= j;

1.4 exchange a[i] and a[j]

2. exchange a[l] and a[j]

実装ではさまざまなことを行っています。

于 2013-10-27T07:34:08.770 に答える