Question
Implement the radixsort algorithm to base 216 for sorting 32-bit unsigned integers given in a linked list. The structure of the linked list is struct
Implement the radixsort algorithm to base 216 for sorting 32-bit unsigned integers given in a linked list. The structure of the linked list is struct listnode { struct listnode * next; unsigned int key;}; You write a function struct listnode * sort(struct listnode * a); which returns the listnodes sorted in increasing order. You do not allocate new nodes (or lose track of the given ones). the test file: #include #include struct listnode { struct listnode * next; unsigned int key; }; struct listnode * sort( struct listnode * list) int main(void) { unsigned int i; struct listnode *list, *tmp; struct listnode space[10000000]; for( i=0; i< 10000000; i++ ) (space[i]).key = 2*((139*i)%10000000); for( i=0; i< 10000000 -1; i++ ) (space[i]).next = &(space[i+1]); (space[10000000 -1]).next = NULL; printf(" Finished preparing list "); fflush(stdout); list = &(space[0]); list = sort( list); for( tmp = list, i=0; tmp != NULL; tmp = tmp->next, i++) ; printf(" before sort: %d list items. ", i); fflush( stdout); for( tmp = list, i=0; tmp != NULL; tmp = tmp->next, i++) ; printf(" after sort: %d list items. ", i); fflush( stdout); for( i=0; i< 10000000; i++ ) { if( list-> key != 2*i ) { printf("something wrong "); fflush(stdout); exit(-1); } list = list-> next; } printf(" all sorted "); fflush(stdout); }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started