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

Question

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

#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

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

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

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

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

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

Answer 2

У вас есть опечатка в коде. С его исправлением он действительно стабилен и имеет сложность 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 3

Mergesort означает split & merge. Расщепление в приведенном ниже фрагменте не является совершенным (это приводит к квадратичному поведению на равномерно распределенное runlengths см комментария от Christoph)), но это будет делать трюк:

#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; 
}