c++ - 使用带有重复的整数的二进制文件进行快速排序。递归遇到问题

Question

首先，我想说这是家庭作业。

很多时候，我们会有一些作业，我会在完成后发布问题，我想继续使用它来提高我的能力，但在这种情况下，我只是难住了！

我们的任务是使用二进制文件实现快速排序，仅使用 file.seek 、 file.read 和 file.write 命令。这是整数的二进制文件。

我遇到的问题是递归部分，在枢轴的“子树”上调用函数。我一直在关注这个网站上提出的算法：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 进行了排序，但索引混淆了，“大小”参数变为负数。

编辑：添加了我的主要内容并根据评论的更改进行了更新。

score 1 · Accepted Answer

我意识到就地 qsort 算法可能不是一个流行的选择，但它使这个特定实例更容易理解。请参阅以下内容：

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <random>
using namespace std;

static void quicksort_stream(std::iostream& st,
                             std::ios::off_type left,  // inclusive
                             std::ios::off_type right, // exclusive
                             unsigned int indent=0)
{
    std::ios::off_type len = (right - left);
    if (len <= 1)
        return;

    // an interesting way of looking at the sort.
    std::string sIndent(indent,' ');
    cerr << sIndent << left << ',' << right << endl;

    // choose a random pivot index form our range:
    std::ios::off_type pivot_idx = left + std::rand() % (len-1);

    // get the pivot value, then swap the *last* value in our
    //  range into the pivot slot. it will be putting the pivot
    //  value in when were done.
    int pivot = 0, val = 0;
    st.seekg(pivot_idx * sizeof(int), ios::beg);
    st.read((char*)&pivot, sizeof(int));
    st.seekg((right-1) * sizeof(int), ios::beg);
    st.read((char*)&val, sizeof(int));
    st.seekg(pivot_idx * sizeof(int), ios::beg);
    st.write((char*)&val, sizeof(int));

    // now start the partition scan.
    pivot_idx = left;
    for (std::ios::off_type i=left; i<(right-1);++i)
    {
        st.seekg(i * sizeof(int), ios::beg);
        st.read((char*)&val, sizeof(int));
        if (val < pivot)
        {
            // swap the current selection with whatever is at
            //  the curent pivot index.
            int val2 = 0;
            st.seekg(pivot_idx * sizeof(int), ios::beg);
            st.read((char*)&val2, sizeof(int));
            st.seekg(i * sizeof(int), ios::beg);
            st.write((char*)&val2, sizeof(int));
            st.seekg(pivot_idx * sizeof(int), ios::beg);
            st.write((char*)&val, sizeof(int));
            ++pivot_idx;
        }
    }

    // store the pivot value back at the pivot index,
    //  placing that value in the last slot of the partition.
    st.seekg(pivot_idx * sizeof(int), ios::beg);
    st.read((char*)&val, sizeof(int));
    st.seekg((right-1) * sizeof(int), ios::beg);
    st.write((char*)&val, sizeof(int));
    st.seekg(pivot_idx * sizeof(int), ios::beg);
    st.write((char*)&pivot, sizeof(int));

    // and finally,invoke on subsequences. skipping the pivot index
    quicksort_stream(st, left, pivot_idx, indent+1);
    quicksort_stream(st, pivot_idx+1, right, indent+1);
}

int main(int argc, char *argv[])
{
    if (argc < 2)
        return EXIT_FAILURE;

    // create a vector of 100 random int values in [1,1000]
    std::vector<int> vals;

    // build generator
    std::random_device rd;
    std::mt19937 rgen(rd());
    std::uniform_int_distribution<> dist(0, 999);
    std::generate_n(std::back_inserter(vals), 100, [&dist,&rgen](){ return dist(rgen); });

    // open the output file and dump this to that location.
    std::fstream fs(argv[1], ios::out|ios::binary);
    fs.write((const char*)vals.data(), vals.size() * sizeof(vals[0]));
    fs.flush();
    fs.close();

    // now open the stream and sort it
    fs.open(argv[1], ios::in|ios::out|ios::binary);
    quicksort_stream(fs, 0, 100);
    fs.flush();
    fs.close();

    // clear the content of the exiting vector.
    std::fill(vals.begin(), vals.end(), 0);
    fs.open(argv[1], ios::in|ios::binary);
    fs.read((char *)vals.data(), vals.size() * sizeof(vals[0]));
    cout << endl << "Sorted" << endl;
    std::copy(vals.begin(), vals.end(), std::ostream_iterator<int>(cout, "\n"));

    return 0;
}

我在其中包含了一个递归缩进的“打印”机制来演示快速排序的本质及其工作原理。示例运行的输出如下所示。我希望它可以帮助你。

样本输出

c++ - 使用带有重复的整数的二进制文件进行快速排序。递归遇到问题

1 回答 1

Related

Reference