@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; > > } -- 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.
