Merge sort circular linked list C -
i trying merge sort list in c. saw code here on french wikipedia gives me incorrect list (i.e not sorted). function compiles though. please note not use top, might take off structure soon. can me figuring out wrong code? had translate algorithm pseudo-code c code. thank you.
p unsorted input list. n length of list.
typedef struct s_stack t_stack; struct s_stack { int nbr; int top; struct s_stack *previous; struct s_stack *next; }; typedef t_stack *pile; t_stack *merge_sort(pile p, int n) { pile q; int q; int p; q = null; q = n / 2; p = n - q; if (p >= 2) { q = merge_sort(p, p); if (q >= 2) p = merge_sort(q, q); } else { q = p->next; } q = fusion(p, p, q, q); return (q); } t_stack *fusion(pile p, int p, pile q, int q) { t_stack *tmp; tmp = null; while (1) { if (p->next->nbr > q->next->nbr) { /* input list (not sorted) circular , checked linked ! reason why need stuff nodes supposed move node q->next after node p */ tmp = q->next; q->next = tmp->next; q->next->previous = q; tmp->previous = p; tmp->next = p->next; p->next->previous = tmp; p->next = tmp; if (q == 1) break; q = q - 1; } else { if (p == 1) { while (q >= 1) { q = q->next; q = q - 1; } break; } p = p - 1; } p = p->next; } return (q); }
your approach bit complicated, problem not simple, yet missed of necessary steps:
merge_sortshould split list in 2 halves , recurse unless list trivial.fusionmust use 3 phases: merging lists taking smallest element each list, appending remainder of first list , appending remaining elements form second list.- it bad idea hide pointers behind
typedefs, makes code less readable.
here corrected version main function testing command line arguments.
#include <stdio.h> #include <stdlib.h> typedef struct s_stack t_stack; struct s_stack { int nbr; int top; struct s_stack *previous; struct s_stack *next; }; t_stack *fusion(t_stack *p, int p, t_stack *q, int q) { t_stack *s; t_stack *e; s = null; while (p > 0 && q > 0) { if (p->nbr <= q->nbr) { /* select element p list */ e = p; p = p->next; p--; } else { /* select element q list */ e = q; q = q->next; q--; } /* detach e */ e->previous->next = e->next; e->next->previous = e->previous; e->next = e->previous = e; if (s == null) { s = e; } else { /* insert e after s */ e->previous = s->previous; e->next = s; s->previous->next = e; s->previous = e; } } if (p > 0) { /* insert p @ end of s */ if (s == null) { s = p; } else { /* insert p after s */ e = p->previous; /* end element of p */ p->previous = s->previous; e->next = s; s->previous->next = p; s->previous = e; } } if (q > 0) { /* insert q @ end of s */ if (s == null) { s = q; } else { /* insert q after s */ e = q->previous; /* end element of p */ q->previous = s->previous; e->next = s; s->previous->next = q; s->previous = e; } } return s; } t_stack *merge_sort(t_stack *s, int s) { t_stack *p; t_stack *q; int p; int q; if (s < 2) { /* single or no elements, sorted */ return s; } /* split p in 2 halves: p[0..p] , q[0..q] */ (q = p = s, p = 0, q = s; p < q; p++, q--) { q = q->next; } p = merge_sort(p, p); q = merge_sort(q, q); s = fusion(p, p, q, q); return s; } t_stack *append(t_stack *s, int value) { t_stack *e = malloc(sizeof(*e)); e->top = 0; e->nbr = value; e->next = e->previous = e; if (s == null) { s = e; } else { /* insert e after s */ e->previous = s->previous; e->next = s; s->previous->next = e; s->previous = e; } return s; } void print_stack(const char *legend, t_stack *s, int s) { printf("%s:", legend); while (s-- > 0) { printf(" %d", s->nbr); s = s->next; } printf("\n"); fflush(stdout); } int main(int argc, char *argv[]) { t_stack *s = null; int s = 0; int i; (i = 1; < argc; i++) { s = append(s, atoi(argv[i])); s++; } print_stack("original stack", s, s); s = merge_sort(s, s); print_stack("sorted stack", s, s); return 0; } 
Comments
Post a Comment