500,000 个已排序整数数组的 C++ 快速排序算法中的段错误

Question

我的 C++ 快速排序算法有问题。我正在运行处理 3 个不同的输入文件，每个文件有 500,000 个整数。第一个和第三个运行正如他们应该的那样，而第二个导致段错误。第一个有 500,000 个未排序的整数，第二个有 500,000 个排序的整数，第三个有 500,000 个倒序的排序整数。我在这里上传了第二个输入文件：http://s000.tinyupload.com/index.php?file_id=43088934371978831513

    #include <iostream>
#include <time.h>

using namespace std;

int unsorted[500010];
int low = 0;
int high = 500000;
int y = 0;
int x  = 0;
int pivot = 0;
void read()
{
    int x;
    for (x = 1; x <= 500001; x++)
    {
        cin>>unsorted[x];
    }
}

void printOut()
{
    int x;
    for (x = 1; x <= 500000; x++)
    {
        //cout<<unsorted[x]<<endl;
        if (unsorted[x - 1] > unsorted[x])
        {
            cout<<"This list is not sorted!"<<endl;
            return;
        }
    }
    cout<<"This list is sorted!"<<endl;
}

int median(int left, int right)
{
    int middle = (right / 2);
    if(unsorted[left] > unsorted[middle] && unsorted[left] < unsorted[right])
        return left;
    else if(unsorted[middle] > unsorted[left] && unsorted[middle] < unsorted[right])
        return middle;
    else if(unsorted[right] > unsorted[middle] && unsorted[right] < unsorted[left])
        return right;

    if(unsorted[left] < unsorted[middle] && unsorted[left] > unsorted[right])
        return left;
    else if(unsorted[middle] < unsorted[left] && unsorted[middle] > unsorted[right])
        return middle;
    else if(unsorted[right] < unsorted[middle] && unsorted[right] > unsorted[left])
        return right;
    else
        return left;
}

void intSwap(int a,int b)
{
    //cout<<"intSwap::   "<<"low: "<<low<<" high: "<<high<<endl;
    int tmp;
    tmp = unsorted[a];
    unsorted[a] = unsorted[b];
    unsorted[b] = tmp;
}

int partition(int low, int high)
{
    //cout<<"partition:: "<<"low: "<<low<<" high: "<<high<<endl;
    x = 0;
    pivot = median(low,high);
    int pivotValue = unsorted[pivot];

    //intSwap(median(low,high),high);
    intSwap(pivot,high);

    int index = low;

    for (x = low; x < high; x++)
    {
        //cout<<"ONE"<<endl;

        if (unsorted[x] <= pivotValue)
        //if (unsorted[x] <= unsorted[index])
        {
            //cout<<"TWO"<<endl;
            intSwap(x, index);
            index += 1;
            //cout<<"THREE"<<endl;
        }
    }
    //cout<<"FOUR"<<endl;
    intSwap(index,high);

    //cout<<"index:: "<<index<<endl;
    return index;
}


void quicksort(int low, int high)
{
    //cout<<"quicksort:: "<<"low: "<<low<<" high: "<<high<<endl;
    int p;
    if (low < high) //else, we're at the end
    {
        p = partition(low, high);
        quicksort(low, p - 1);
        quicksort(p + 1, high);
    }
}

int main()
{
    read();
    cout<<"read complete"<<endl;

    clock_t t = clock();
    quicksort(1,500000);
    t = clock() - t;
    printOut();
    cout<<"It took me "<<t<<" clicks ("<<((float)t/CLOCKS_PER_SEC)<<" seconds)"<<endl;
    //partition();
    //cout<<unsorted[median(0,500000)]<<endl;
    //quicksort();
}

gdb 告诉我程序在这里出现段错误：

Program received signal SIGSEGV, Segmentation fault.
0x08048984 in partition (low=424752, high=500000)
at quicksort.cpp:69
69          pivot = median(low,high);

如果有人能帮我一把，我将不胜感激！请注意，该算法可能需要几分钟才能运行!

Answer 1

一行看起来很奇怪：

int middle = (right / 2);

这并不总是return左右之间的元素。

也许试试：

int middle = left + ( (right-left) / 2);

当前代码可能会产生一个不会减少数组长度的枢轴值，因此您最终会遇到无限递归，当所有堆栈 space 用完时最终会崩溃。

500,000 个已排序整数数组的 C++ 快速排序算法中的段错误

Seg Fault in c++ quicksort algorithm on array of 500,000 sorted integers

c++

algorithm

sorting

segmentation-fault

quicksort