On Jul 13, 2:46 pm, Devendra Pratap Singh <[email protected]> wrote: > @gene > > thanx for the working code > > but can u explain its working more clearly > > On Jul 13, 11:21 pm, Gene <[email protected]> wrote: > > > > > On Jul 10, 5:18 pm, Gene <[email protected]> wrote: > > > > On Jul 9, 3:55 pm, Devendra Pratap Singh <[email protected]> > > > wrote: > > > > > plz write a code to > > > > > Sort n integer in the range 1 to n^2 in O(n) > > > > Use radix sort with radix n. Three O(n) passes will always do the > > > job. If you subtract 1 from each value so the range is 0 to n^2-1, two > > > passes will be enough. > > > Nice lunchtime puzzle. Here is some code for your pleasure: > > > #include <stdio.h> > > #include <stdlib.h> > > > #define MAX_SIZE (10 * 1024) > > struct node_s { > > int next, val; > > > } nodes[MAX_SIZE]; > > > // Radix-n sort descending. Assumes data are non-negative. > > // Will take K passes if largest datum does not exceed n^K. > > int sort_descending(struct node_s *nodes, int n) > > { > > int i, k, head, next, shifted, digit, more_p, n_passes, div; > > int buckets[MAX_SIZE]; > > > // Chain nodes into a single list. > > head = 0; > > for (i = 0; i < n; i++) > > nodes[i].next = i + 1; > > nodes[n - 1].next = -1; > > > // Make passes until all remainders are zero. > > // Always 2 if max datum is less than n^2. > > n_passes = 0; > > div = 1; > > do { > > // Empty the buckets. > > for (k = 0; k < n; k++) > > buckets[k] = -1; > > // Fill the buckets, noting whether we need more passes. > > more_p = 0; > > for (i = head; i != -1; i = next) { > > next = nodes[i].next; > > shifted = nodes[i].val / div; > > digit = shifted % n; > > nodes[i].next = buckets[digit]; > > buckets[digit] = i; > > if (shifted >= div) more_p = 1; > > } > > // Concatenate the buckets. > > head = -1; > > for (k = 0; k < n; k++) { > > for (i = buckets[k]; i != -1; i = next) { > > next = nodes[i].next; > > nodes[i].next = head; > > head = i; > > } > > } > > n_passes++; > > div *= n; > > } while (more_p); > > printf("sort took %d passes\n", n_passes); > > return head; > > > } > > > int main(void) > > { > > int i, n, head, last; > > > n = 500; > > for (i = 0; i < n; i++) > > nodes[i].val = rand() % (n * n); > > head = sort_descending(nodes, n); > > // Make sure we're sorted descending and print. > > last = -1; > > for (i = head; i != -1; i = nodes[i].next) { > > printf("%d ", nodes[i].val); > > if (last != -1 && nodes[i].val > last) { > > printf("oops!\n"); > > return 1; > > } > > last = nodes[i].val; > > } > > printf("\n"); > > return 0; > > > }
Google for radix sort. After reading the Wikipedia article, the comments in the code should make sense. We're building the radix buckets as singly linked lists and then concatenating all the lists to implement the merge pass. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
