1

まず、これは宿題だと言いたいです。

多くの場合、完了後に質問を投稿する課題があり、能力を向上させるために引き続き取り組みたいと思いますが、この場合は困惑しています!

file.seek 、 file.read 、および file.write コマンドのみを使用して、バイナリ ファイルを使用してクイックソートを実装するタスクが課されました。これは整数のバイナリ ファイルです。

私が抱えている問題は、ピボットの「サブツリー」で関数を呼び出す再帰部分です。私はこの Web サイト ( http://xoax.net/comp_sci/crs/algorithms/lessons/Lesson4/ ) に掲載されているアルゴリズムに従っており、コード例をバイナリ ファイル実装の疑似コードとして使用しています。

これが私のコードです：

//Algorithm and code example used:
void manage( fstream & file , int lindex , int fSize ){


    //Chunks of 1 or 0 do not need sorting
    if( fSize <= 1 )
        return;

    //Choose point in file as "pivot." Pivot is a value.
    //pp is the index of "pivot"
    int pp = (rand() % fSize) + lindex;
    file.seekp( pp * sizeof( int ) , file.beg );
    int pivot;
    file.read( (char*)&pivot , sizeof( int ) );

    //Choose "indices" to be swapped. These will be used in seekp
    int leftIndex = lindex;
    int rightIndex = fSize - 1;

    //Swap val , swap val, temp storage, swap index 1 , swap index 2
    int leftSwap , rightSwap , temp , tempI1 , tempI2 = 0;

    //Dummy indecies to help with tracking partitions.
    int dumL = leftIndex;
    int dumR = rightIndex;

    while( dumL < dumR ){

        //Move to left index from the file beginning.
        file.seekp( dumL * sizeof( int ) , file.beg );

        do{

            tempI1 = file.tellp() / sizeof( int );
            dumL = tempI1;
            file.read( (char*)&temp , sizeof( int ) );
        }

        while( temp < pivot );

        leftSwap = temp;

        //Move to right index.
        file.seekp( dumR * sizeof( int ) , file.beg );
        int n = 1;

        do{

            tempI2 = file.tellp() / sizeof( int );
            dumR = tempI2;
            file.read( (char*)&temp , sizeof( int ) );
            file.seekp( ( rightIndex - n ) * sizeof( int ) , file.beg );
            n++;
        }           

        while( temp > pivot );

        rightSwap = temp;

        //Swap values
        int hold = 0;

        if( leftSwap == rightSwap && rightSwap == pivot )
            break;

        file.seekp( tempI1 * sizeof( int ) , file.beg );
        file.read( (char*)&hold , sizeof( int ) );

        file.seekp( tempI1 * sizeof( int ) , file.beg );
        file.write( (char*)&rightSwap , sizeof( int ) );

        file.seekp( tempI2 * sizeof( int ) , file.beg );
        file.write( (char*)&leftSwap , sizeof( int ) );
    }

    cout << "pp: " << pp << endl;
    cout << "dumL: " << dumL << endl;
    cout << "dumR: " << dumR << endl << endl;

    //cout << "Lmanage: \n\t Lindex: 0\n\tSize: " << dumL << endl;
    manage( file , 0 , dumL );
    //cout << "Rmanage: \n\t Lindex: " << dumL + 1 << "\n\tSize: " << fSize - dumL - 1 << endl;
    manage( file , dumL + 1 , fSize - (dumL - leftIndex) - 1 );
}


void quicksort( fstream & file , int iSize ){

    srand( ( unsigned int ) time( 0 ) );
    manage( file , 0 , iSize );
}


int main( int argc, char* argv[] ){

    if( argc != 2 ){

        cout << "Invalid number of arguments.\n";
        return -1;
    }

    fstream file;
    int x = 0;

    file.open( argv[1] , ios::binary | ios::out | ios::in );

    //Calculate number of ints in file.
    file.seekg( 0 , file.end );
    int size = file.tellg() / sizeof( int );

    cout << "size: " << size << endl;

    quicksort( file , size );

    return 0;
}

「arg」は、100 個の整数を含むバイナリ ファイルであり、重複する可能性があります。問題は、最初の 1/4 をソートしているように見えますが、インデックスが混同され、「サイズ」引数が負になることです。

編集：私のメインを追加し、コメントからの変更で更新しました。

4

1 に答える 1