Quick sort linked list C++

Code quick sort voi linkedlist

#include #include #include typedef struct node node; struct node{ int value; node * next; }; typedef struct list list; struct list{ node * head, *last; }; list * make_list(){ list * L=(list *)malloc(sizeof(list)); L->head=L->last=NULL; return L; } node * make_node(int value){ node * n=(node *)malloc(sizeof (node)); assert(n); n->value=value; n->next=NULL; return n; } node * append(list * L, int value){ // them vao cuoi danh sach, tra ve node dc tao thanh node * newNode=make_node(value); if(L->head==NULL){ L->head=L->last=newNode; }else{ L->last->next=newNode; L->last=newNode; } return newNode; } void * free_list(list * L){ node *p=L->head; while(p){ node * t=p->next; free(p); p=t; } L->head=L->last=NULL; } void print_list(list *L){ node *p=L->head; while(p){ printf("%d -> ",p->value); p=p->next; } printf("\n"); } void quick_sort(list *L){ if(!L->head || !L->head->next){ return; } list * lower=make_list(); list * upper=make_list(); int pivot=L->head->value; node *p; for(p=L->head->next; p!=NULL; p=p->next){ if(p->value>=pivot){ append(upper,p->value); }else{ append(lower,p->value); } } quick_sort(lower); append(lower,pivot); quick_sort(upper); lower->last->next=upper->head; lower->last=upper->last; free_list(L); L->head=lower->head; L->last=lower->last; } int main() { list *L=make_list(); append(L, 1); append(L,3); append(L,2); append(L,5); append(L,4); puts("# before quick sort:"); print_list(L); quick_sort(L); puts("# after quick sort: "); print_list(L); return 0; }

###ouput

# before quick sort: 1 -> 3 -> 2 -> 5 -> 4 -> # after quick sort: 1 -> 2 -> 3 -> 4 -> 5 ->

quick sort 10^5 phan tu [0,10000)

int main() { list *L=make_list(); int n=100000; int i; srand(time(NULL)); for(i=0;itime ~ 0.19s

Top List List

Quick sort linked list C++

quick sort 10^5 phan tu [0,10000)

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội