c - 需要帮助查找 C 中快速排序实现错误的原因

Question

我在 Xcode 中遇到一些奇怪的错误 - 线程 1:在下面的代码段中的 EXC_BAD_ACCESS

while(*w1 != '\0' && *w2 != '\0')

这里是快速排序的实现和比较方法:

void quicksort(char ***words, int start, int end){ //start is pivot
    if(start >= end){
        return;
    }
    int left = start;
    int right = end;

    int comp;
    while( left <= right ){
        do{
            char* w1 = (*words)[++left];
            char* w2 = (*words)[start];
            comp = compare(w1, w2);
        }while(comp < start); //while current left less than pivot

        do{
            char* w1= (*words)[--right];
            char* w2= (*words)[start];
            comp = compare(w1, w2);
        }while(comp >= start); //while current right is more or equal to pivot

        if(left < right){
            swap(words, left, right);
        }
    }
    swap(words, start, --left);
    quicksort(words, 0, left-1);
    quicksort(words, left+1, end);
}

int compare(char *w1, char *w2){
    while(*w1 != '\0' && *w2 != '\0'){
        if( *w1 < *w2 ){
            return -1;
        }else if( *w1 > *w2 ){
            return 1;
        }else{
            w1++;
            w2++;
        }
    }

    if(*w1 == *w2)
        return 0;
    else if(*w1 == '\0')
        return -1;
    else return 1;
}

这是完整代码 http://ideone.com/MZFaFO

我假设问题的原因可能在 do-while 之间。我用指针做的很糟糕..我将非常感谢你的帮助。我刚开始学习 C，它完全杀死了我。 :(

Answer 1

有很多错误(稍后会详细介绍)，但我必须以这个开头:

不要为快速排序实现传递右/左索引标记。你不需要它们，它们给通用算法带来的复杂性是不值得的。这是 C。这样你就可以免费进行指针运算。用它; Revel 其中。这样一来，您的算法就减少到一个完成偏移魔术的地方。剩下的就变得微不足道了。

但首先，从您的比较器开始，进行一些一般性的内务处理。这是否更简单，由您来判断:

int compare(char const *w1, char const *w2)
{
    while(*w1 && *w2)
    {
        if (*w1 < *w2)
            return -1;

        if (*w2++ < *w1++)
            return 1;
    }
    return *w2 ? -1 : (*w1 != 0);
}

这里唯一值得一提的是最后一个子句，它说:“如果我们完成 w2 仍然指向某物，它必须比 w1 长，所以 w1 是“less”，我们返回 -1。否则，w2 必须在字符串末尾，所以如果 w1 是，则返回 1不是(因此“更大”)，否则返回 0(它们都在字符串末尾)。

关于 swap 元素。您所做的只是交换指针数组中的指针 值(地址)。因此……

void swap_ptrs(char **lhs, char **rhs)
{
    char *tmp = *lhs;
    *lhs = *rhs;
    *rhs = tmp;
}

关于您的问题的实质(有多个)。首先，您到底想用这个完成什么:

    do{
        char* w1 = (*words)[++left];
        char* w2 = (*words)[start];
        comp = compare(w1, w2);
    }while(comp < start)

start 是指针数组的索引，comp 是比较的结果。它不返回索引，它返回 -1、0 或 1。他们之间确实没有关系。同样的问题发生在你的第二个 while 循环中。此外，您正在递增 left(并在另一个循环中递减 right)过早地。简而言之，这根本无法快速排序 。

利用前面提到的指针数学以及提供的比较器和交换例程，这是一种对相关分区进行快速排序的方法。请注意，我们只需要两个参数:数组的基地址和我们希望排序的序列的长度。递归使用指针算法在需要时提供正确的起点和长度。

void quicksort(char **words, size_t len)
{
    if (len < 2)
        return;

    char const *pvt = words[len/2];
    size_t lhs = 0, rhs=len-1;

    while( lhs < rhs )
    {
        while (compare(words[lhs], pvt) < 0)
            ++lhs;

        while (compare(words[rhs], pvt) > 0)
            --rhs;

        if (lhs <= rhs)
            swap_ptrs(words+lhs++, words+rhs--);
    }

    quicksort(words, rhs+1);
    quicksort(words+lhs, len-lhs);
}

为了测试这个，一个简单的 random-string-generationg 实现:

int main()
{
    srand((unsigned int)time(NULL));

    // allocate a string bed of 100 pointers
    static const size_t len = 100;
    char **arr = malloc(sizeof(*arr) * len);

    // populate with random strings ranging from 5 to 8 chars.
    for (size_t i=0; i<len; ++i)
    {
        int siz = 5 + rand() % 4;
        arr[i] = malloc(siz+1);
        for (size_t j=0; j<siz; ++j)
            arr[i][j] = 'A' + rand() % 26;
        arr[i][siz] = 0;
    }
    quicksort(arr, len);

    for (size_t i=0; i<len; ++i)
    {
        printf("%s\n", arr[i]);
        free(arr[i]);
    }
    free(arr);
}

输出(显然不同)

ARSXTGA
ATQYX
BCFNHSN
BEDYEW
BGTYDCK
BSYNEB
BYQXH
BYXVID
CHXQVEVG
CLRLYLO
DEXTPQO
DXHAIP
ECLMAD
EPYCQJ
EPZGNCG
EUUWTXOI
FEABB
FFMCTK
FYOIIKX
FZQWIQ
GDDUOMO
GFJNWEKP
GGMHDPA
GQMSEU
HTPCU
HULIENC
IGNHGIMM
ITFPMUAM
IYHBOWJ
IYTDAOEE
JEQVXRZ
JMUCWRV
JUDMWMS
KHVKN
KJOJXNL
KQIVURG
KVIGK
KVUYIER
LACVY
LCEKGER
LGELOIY
MILDEFJI
MNZDX
MOBOAPYL
MOLDKACO
MUJXDGH
NDZZLRQD
NEZTSBPC
NLDHM
OAZSW
OLPKKL
OZOBK
PBIOISM
PCYHNYQ
PEZMH
PFWEJQI
PIXNQ
PZATCAIK
QJUYGNID
QKGDXI
QLGORE
QULGW
RBEDK
ROYSAPGH
RQTVMO
RTBGDBXM
SLHUOE
SLTBOETM
SNRIGY
SRBPOF
STGPU
STUOQ
SXZFPRR
TBRFT
TELZYQ
TJKWLLE
TKLSNN
TNATOPFQ
UJXGWM
UNQZSF
VCLZUWSV
VPJVAEP
WBVBY
WDVWTEF
WEPRL
WFTJSFIQ
WUIJQS
WWPOAQQ
XLASZMI
XOQTSPZ
XQZZSZ
YFHXA
YFXMKAC
YPPUC
YRLVS
YTGHWVU
YWXOWXL
ZLVTUL
ZUNMCE
ZUUQZXLX