在双向链接列表上的QuickSort无法正常工作 [英] QuickSort on a doubly linked list not working as it should

问题描述

我使用了过去用于数组的算法.这总是选择第一个元素作为枢轴.这是代码:

I used an algorithm that I've used in the past for arrays. This always picks the first element as the pivot. Here's the code:

void quickSort(int a[],int l,int r,int *count)
{
    if(l<r-1)
    {
        *count=*count+r-l-1;
        int q=partition(a,l,r); //finding the pivot position in sorted array
        quickSort(a,l,q-1,count);     //recursive calling before pivot sub array
        quickSort(a,q+1,r,count);     //recursive calling after pivot sub array
    }
}

//partition function definition
int partition(int a[],int l,int r)
{
    int j,temp,i=l+1;

    for(j=l+1;j<r;j++)
    {
        //swap values if a[j]<=a[r](i.e. pivot)
        if(a[j]<=a[l])
        {
            temp=a[j];
            a[j]=a[i];
            a[i]=temp;
            i++;
        }
    }
    //place pivot at its position by swapping
    temp=a[i-1];
    a[i-1]=a[l];
    a[l]=temp;
    return i;
}

现在是当我尝试将其实现到双向链接列表时."head"代表链接列表的

Now here is when I try to implement this to a doubly linked list. "head" represents the head to the linked list

void recQuick(void* head, node* s, node* e, int (*comparator)(void*,void*)) {    
    //s = (node*) head;


    if ( e != NULL && s != e && s != e->next ) { //we want to cycle through the linked list

        node* pivot = (node*) realQuickSorter(head,s,e,(comparator)); 


        recQuick(head,s,pivot->prev, (comparator));

        recQuick(head,pivot->next,e, (comparator));
    }

    //return 1;

}

node* realQuickSorter ( void* head, node* s, node* e, int (*comparator)(void*,void*)) { 

    char* piv = s->str; //will always be the first element

    node* leader = s->next;

    //node* ii = s->next;

    node* follower = leader;


    for ( follower = leader; follower != e ; follower = follower->next ) {

        if ( ((comparator)(follower->str,s->str)) == 1 ) { //pivot is bigger, we need to swap

            swap(&(follower->str),&(leader->str));

            leader = (leader == NULL) ? s : leader->next;
            //leader = leader->next;
        }

    }

    swap(&(s->str),&(leader->prev->str));

    return leader->prev;
}

swap，bringMeEnd之类的功能是正确的

Functions like swap, bringMeEnd are correct

链表版本似乎仅在乱序时才交换前两个，而其余的保持不变

The linked list version only seems to swap the first two when out of order, leaving the rest the same

推荐答案

假设 e 是指向子列表中最后一个节点的指针，则realQuickSorter()中的for循环在比较之前停止枢轴的最后一个节点.可能还有其他问题.

Assuming that e is a pointer to the last node in a sub-list, the for loop in realQuickSorter() stops before comparing the last node with the pivot. There may be other issues.

如果包括比较和交换功能以及生成测试列表并调用recQuick()的代码，这将有所帮助.

It would help if compare and swap functions were included, as well as the code that generates the test list and calls recQuick().

这是基于原始问题的示例代码.修复程序在注释中注明.我更改了变量名称以匹配我的一些旧代码.名称 follower 和 leader 从使用的方式开始倒排.在我的示例代码中，我切换为使用 pi 和 pj 作为指向等效于索引 i 和 j 用于数组.我颠倒了compare函数的含义，使其与strcmp相同(假设目标是从最低到最高的字符串值进行排序).

Here is example code based on the original question. The fixes are noted in comments. I changed variable names to match some old code I had. The names follower and leader were backwards from the way they are used. In my example code, I switched to using pi and pj, as pointer to node equivalents to indexes i and j as used for arrays. I reversed the sense of the compare function to be the same as strcmp (assuming the goal is to sort from lowest to highest string value).

recQuick缺少对lo( s )== NULL的检查，如果枢轴最终出现在第一个节点(pivot-> prev == NULL)中，则可能会发生这种情况.realQuickSorter 需要两个修复:在与枢轴进行比较时包括最后一个节点(hi 或 e).如果枢轴结束于最后一个节点，则pi( leader )可能会以NULL结尾(如果hi-> next == NULL)，则进行检查并将pi设置为hi in在这种情况下，否则将其设置为pi->上一个.

recQuick was missing a check for lo (s) == NULL, which can happen if the pivot ends up in the first node, where pivot->prev == NULL. realQuickSorter needed two fixes: include the last node (hi or e) when comparing versus pivot. If the pivot ends up in the last node, then pi (leader) may end up as NULL (if hi->next == NULL), so a check is made and pi is set to hi in this case, else it's set to pi->prev.

typedef struct node_{
    struct node_ * next;
    struct node_ * prev;
    char * str;
}node;

void recQuick(node* lo, node* hi, int (*comparator)(void*,void*))
{
    node* pv;
    if(lo == NULL || hi == NULL || lo == hi || lo == hi->next) /* fix */
        return;
    pv = (node*) realQuickSorter(lo,hi,(comparator));
    recQuick(lo, pv->prev, (comparator));
    recQuick(pv->next, hi, (comparator));
}

node* realQuickSorter(node* lo, node* hi, int (*comparator)(void*, void*))
{ 
    node* pi = lo->next;
    node* pj;
    for(pj = pi; pj != hi->next ; pj = pj->next ){  /* fix */
        if(((comparator)(pj->str, lo->str)) <= 0 ){ /* changed comparator */
            swap(&(pj->str),&(pi->str));
            pi = pi->next;                          /* fix */
        }
    }
    if(pi == hi->next)                              /* fix (hi->next could be NULL) */
        pi = hi;                                    /* fix */
    else                                            /* fix */
        pi = pi->prev;                              /* fix */
    swap(&(lo->str),&(pi->str));                    /* fix */
    return pi;                                      /* fix */
}

---

这是对链表进行排序的一种无效方法.M Oehm的答案应该更好一些，但是对链表进行自下而上的合并排序会更快:

---

This is an inefficient way to sort a linked list. M Oehm's answer should be a bit better, but a bottom up merge sort for linked list would be faster:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

在节点分散的大型列表上，尽管使用了哪种算法，但每个节点访问都可能涉及缓存未命中.假设有足够的内存，则将列表数据复制到数组中，对数组进行排序并创建新的链接列表会更快.

On a large list with scattered nodes, despite what algorithm is used, every node access could involve a cache miss. Assuming enough memory, it would be faster to copy the list data into an array, sort the array, and create a new linked list.

这篇关于在双向链接列表上的QuickSort无法正常工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！