Быстрая сортировка в двусвязном списке не работает должным образом

Question

Я использовал алгоритм, который я использовал в прошлом для массивов. Это всегда выбирает первый элемент как стержень. Вот код:

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» представляет заголовок связанного списка

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, takeMeEnd верны

Версия связанного списка, кажется, только меняет первые две, когда выходит из строя, оставляя остальное же

Answer 1

Если предположить, что e - указатель на последний узел в подсписке, то для l oop в realQuickSorter () останавливается перед сравнением последнего узла с осью. Могут быть и другие проблемы.

Было бы полезно, если бы были включены функции сравнения и обмена, а также код, который генерирует список тестов и вызывает recQuick ().

---

Здесь Пример кода на основе исходного вопроса. Исправления отмечены в комментариях. Я изменил имена переменных, чтобы они соответствовали старому коду. Имена follower и leader были обратными от того, как они используются. В моем примере кода я переключился на использование pi и pj в качестве указателя на эквиваленты узла для индексов i и j, используемых для массивов. Я изменил смысл функции сравнения на тот же, что и для strcmp (предполагая, что целью является сортировка от строкового значения к наименьшему).

recQuick пропустил проверку на lo (s) == NULL , что может произойти, если сводка заканчивается в первом узле, где pivot-> prev == NULL. Для realQuickSorter потребовалось два исправления: включить последний узел (hi или e) при сравнении с pivot. Если пивот заканчивается в последнем узле, то pi (leader) может закончиться как NULL (если hi-> next == NULL), поэтому выполняется проверка, и в этом случае pi устанавливается на hi, иначе это установите 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 */
}

---

Это неэффективный способ сортировки связанного списка. Ответ М Оема должен быть немного лучше, но сортировка слиянием снизу вверх для связанного списка будет быстрее:

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

В большом списке с разбросанные узлы, несмотря на то, какой алгоритм используется, каждый доступ к узлу может включать в себя промах кэша. При условии, что памяти достаточно, было бы быстрее скопировать данные списка в массив, отсортировать массив и создать новый связанный список.

Answer 2

Вы пытаетесь реализовать быструю сортировку для связанных списков на основе уже существующей реализации для массивов. Вы делаете это, меняя значения узлов. На мой взгляд, это не идеально. Связанные списки не являются массивами. Вместо этого вы должны поменять местами узлы.

(Вероятно, причина в том, что ваши данные существуют в виде связанного списка. Если полезная нагрузка на узлы велика, обмен данными неэффективен. Если у вас есть внешние указатели на узлы, подкачка сделает их недействительными.)

Как работает быстрая сортировка?

• Выберите сводку и удалите ее из списка.
• Разделите оставшийся список на
  1. элементов, которые меньше, чем элементы pivot ( le ),
  2. , равные элементу pivot, и элементы
  3. , превышающие значение элемента pivot ( gt ) на несколько метри c.
• Запустите quicksort для разделов, чтобы ваш список теперь выглядел следующим образом:
  sorted le partition | стержень | sorted gt partition

В реализации массива вы достигнете этого, меняя элементы вокруг и перемещая шарнир. Это хорошая стратегия, потому что таким образом вам нужно дополнительное пространство.

В связанном списке вы можете создавать разделы, извлекая текущий список в два списка разделов. Вызовите их с помощью быстрой сортировки, а затем снова соедините их вместе с центральной точкой.

Если у вас есть списки с множеством элементов, которые имеют одинаковое значение, т. Е. Сравнивают одинаково, вы можете сделать одноузловую точку третий список, eq .

Вот код, который делает это. Функции

• pop, которые выводят первый узел из списка;
• append, который добавляет узел в конец списка, и
• join, который добавляет второй список к первому

, не отображаются, но сам алгоритм должен быть понятным. Это довольно просто. Каждый узел имеет next и ´prev pointer as well as some data ; a list has head and tail` указатели.

В любом случае, здесь идет:

void quicksort(List *list)
{
    if (list->head != list->tail) {
        List eq = {NULL, NULL};
        List lt = {NULL, NULL};
        List gt = {NULL, NULL};

        append(&eq, pop(list));

        while (list->head) {
            Node *node = pop(list);

            int cmp = compare(node->data, eq.head->data);

            if (cmp < 0) {
                append(&lt, node);
            } else if (cmp > 0) {
                append(&gt, node);
            } else {
                append(&eq, node);
            }
        }

        quicksort(&lt);
        quicksort(&gt);

        join(list, &lt);
        join(list, &eq);
        join(list, &gt);
    }
}

Этот метод сортировки стабилен : Элементы с одинаковым значением имеют одинаковый порядок в отсортированном и исходном списке. Полный пример программы, которая включает в себя функции pop, join и extract: здесь на ideone .