1

機能するクイックソートプログラムを作成しました。反復回数をカウントするカウンターを含める必要があります。クラスではアルゴリズムについて話し、要素の比較が基本的な操作であると結論付けました。しかし、カウンターをどこに置くべきかよくわかりません。正しい出力が得られないようです。私は自分のコードを含めました、ありがとう！

void partition( vector<int> & S, int low, int high, int & pivotpoint )
{
vector<int> U;
int pivotitem = S.at(low);
int j = low;
int i;
for( i = low + 1; i <= high; i++)
    if( S.at(i) < pivotitem)
    {
        j++;
        swap( S[i], S[j] );
    }
pivotpoint = j;
swap( S[low], S[pivotpoint] );
}

void quicksort( vector<int> & S, int low, int high, int &basic_ops )
{
int pivotpoint = low;
if( high > low) 
{   
    partition( S, low, high, pivotpoint );
    quicksort( S, low, pivotpoint -1, basic_ops );
    quicksort( S, pivotpoint + 1, high, basic_ops );
}   
}
4

2 に答える 2

0

  1. クイックソートをクイックソート (配列、0、長さ -1、カウンターへのポインター) として呼び出す

    void quicksort( vector<int> & S, int low, int high, int &basic_ops )

{

int pivotpoint = low;
if( high > low) 
{

    *basic_ops += high - low;

    partition( S, low, high, pivotpoint );

    quicksort( S, low, pivotpoint -1, basic_ops );

    quicksort( S, pivotpoint + 1, high, basic_ops );

}

}
于 2013-02-18T10:41:59.147 に答える
0

ピボットが変更されている場所にカウンターを置きます

于 2013-02-18T14:48:52.340 に答える