сложность слияния со связанным списком

Question

У меня есть код для сортировки слиянием с использованием связанного списка, он работает нормально, мой вопрос, в чем сложность этого алгоритма? Это O (nlog (n))? Также он стабилен? Мне интересно, потому что, как я знаю, Mergesort стабилен, как насчет использования связанного списка? если у нас есть элементы с некоторыми равными друг другу, этот код сохраняет порядки элементов? большое спасибо

#include<stdio.h>
#include <stdlib.h>
struct node
{
    int number;
    struct node *next;

};
struct node *addnode(int number,struct node *next);
struct node*mergesort(struct node *head);
struct node *merge(struct node *one,struct node *two);

int main(void){
    struct node *head;
    struct node *current;
    struct node *next;
    int test[]={8,3,1,4,2,5,7,0,11,14,6};
    int n=sizeof(test)/sizeof(test[0]);
    int i;
    head=NULL;
     for (i=0;i<n;i++)
         head=addnode(test[i],head);
     i=0;
     head=mergesort(head);
    printf("before----after sort \n");
    for (current=head;current!=NULL;current=current->next)
        printf("%4d\t%4d\n",test[i++],current->number);

    /* free list */
    for (current=head;current!=NULL;current=current->next)
        next=current->next;free(current);
return 0;
}

struct node *addnode(int number,struct node* next){
    struct node *tnode;
    tnode=(struct node*)malloc(sizeof(*tnode));
    if(tnode!=NULL){
        tnode->number=number;
        tnode->next=next;
            }

     return tnode;
     }
struct node *mergesort(struct node *head){

    struct node *head_one;
    struct node *head_two;
    if((head==NULL) ||(head->next==NULL))
         return head;
    head_one=head;
    head_two=head->next;
    while( (head_two!=NULL) &&(head_two->next!=NULL)){
        head=head->next;
        head_two=head->next->next;
        }
    head_two=head->next;
    head->next=NULL;
    return merge(mergesort(head_one),mergesort(head_two));
    }
struct node *merge(struct node*head_one,struct node*head_two){

    struct node *head_three;
    if(head_one==NULL)
         return head_two;
    if(head_two==NULL)
         return head_one;
    if(head_one->number<head_two->number){

head_three=head_one;
head_three->next=merge(head_one->next,head_two);
    }
    else
    {

        head_three=head_two;
        head_three->next=merge(head_one,head_two->next);


    }

    return head_three;
    }

Answer 1

В вашем коде есть опечатка. После исправления он действительно стабилен и имеет O(n log n) сложность. Хотя, чтобы быть уверенным, вы действительно должны переопределить свой merge как цикл вместо рекурсии. В C нет оптимизации хвостового вызова (верно?), Так что это может привести к путанице:

struct node *mergesort(struct node *head){

    struct node *head_one;
    struct node *head_two;
    if((head==NULL) ||(head->next==NULL))
         return head;
    head_one=head;
    head_two=head->next;
    while( (head_two!=NULL) &&(head_two->next!=NULL)){
        head=head->next;
        // head_two=head->next->next;      // -- the typo, corrected:
        head_two=head_two->next->next;
        }
    head_two=head->next;
    head->next=NULL;
    return merge(mergesort(head_one),mergesort(head_two));
    }

И пока мы на этом, изменим ваш рабочий процесс с

    return merge(mergesort(head_one),mergesort(head_two));

до

    struct node *p1, *p2; 
    // ......
    p1 = mergesort(head_one);
    p2 = mergesort(head_two);
    return merge(p1,p2);

таким образом в стеке будет намного проще (будет использовать гораздо меньше).

В общем, это то, что известно как нисходящий mergesort. Вы также можете сделать это по принципу снизу вверх , сначала отсортировав последовательные порции по два элемента каждый, затем объединяя их в (таким образом, теперь отсортированные) порции по 4 элемента, затем объединяя эти попарно, на куски по 8 элементов и т. д., пока не останется только один кусок - отсортированный список.

Чтобы получить дополнительную фантазию (и эффективность), вместо того, чтобы начинать с 2-х блоков, начните с разделения списка на монотонные запуски , то есть увеличение последовательностей и уменьшение последовательностей - повторное связывание последних в обратном порядке - таким образом, сегментируя исходный список в соответствии с его внутренним порядком, так что, вероятно, будет меньше начальных кусков для слияния; затем продолжайте объединять эти попарно , как и прежде, до тех пор, пока в конце не останется только один.

Answer 2

Слияние означает разделение и слияние.Расщепление в приведенном ниже фрагменте не является идеальным (оно приводит к квадратичному поведению при одинаково распределенных длинах прогона, см. Комментарий Кристофа)), но это поможет:

#include <stdio.h>
#include <string.h>

struct llist {
        struct llist *next;
        char *payload;
        };

int llist_cmp(struct llist *l, struct llist *r);
struct llist * llist_split(struct llist **hnd
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_merge(struct llist *one, struct llist *two
                        , int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_sort(struct llist *ptr
                        , int (*cmp)(struct llist *l, struct llist *r) );

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;

for (save=NULL, tail = &save; this = *hnd; ) {
        if (! this->next) break;
        if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
        *tail = this->next;
        this->next = this->next->next;
        tail = &(*tail)->next;
        *tail = NULL;
        }
return save;
}

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}
struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *save;

save=llist_split(&ptr, cmp);
if (!save) return ptr;

save = llist_sort(save, cmp);

return llist_merge(ptr, save, cmp);
}

int llist_cmp(struct llist *l, struct llist *r)

{
if (!l) return 1;
if (!r) return -1;
return strcmp(l->payload,r->payload);
}


struct llist lists[] =
{{ lists+1, "one" }
,{ lists+2, "two" }
,{ lists+3, "three" }
,{ lists+4, "four" }
,{ lists+5, "five" }
,{ lists+6, "six" }
,{ lists+7, "seven" }
,{ lists+8, "eight" }
,{ lists+9, "nine" }
,{ NULL, "ten" }
        };

int main()
{
struct llist *root,*tmp;

root = lists;

fprintf(stdout, "## %s\n", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }

fprintf(stdout, "## %s\n", "sorting..." );
root = llist_sort(root, llist_cmp);
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%s\n", tmp->payload);
        }
fprintf(stdout, "## %s\n", "done." );

return 0;
}

Answer 3

Как не реализовать сортировку слиянием для связанных списков

• не рекурсивно делить пополам список - произвольный доступ не бесплатный
• не делятся на подсписки размером 1 и n - 1, как объясняется ruakh

Как реализовать сортировку слиянием для связанных списков

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

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