Implement the radixsort algorithm to base 216 for sorting 32-bit unsigned intege

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

Explanation / Answer

struct listnode { u32 Key; listnode *next; }; template Sortable *rsorti(Sortable *head, Sortable lists[], Sortable *tails[]) { while(head) { u32 bucket = (head->sortKey >> shift) & 0xff; tails[bucket]->next = head; tails[bucket] = head; head = head->next; } Sortable list; Sortable *prev = &list; for (unsigned int n=0;nnext = lists[n].next; prev = tails[n]; lists[n].next = NULL; tails[n] = &lists[n]; } } prev->next = NULL; return list.next; } template T *rsort(T *head) { Sortable lists[256]; Sortable *tails[256]; if (!head) return NULL; for (unsigned int n=0;n

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---