Thread: Radix Sorting Help

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    26

    Radix Sorting Help

    Hi everyone,

    I'm having trouble implementing a supposedly simple Least Significant Digit first Radix Sort. The book I'm using gave me somewhat of a template that I touched up (below), but I'm very unsure of where to start. I know the basic layout (Initialization of memory space, Distribution of numbers in bins, and then Collection of the bins), but I don't know how to code it. The examples I've seen don't pertain to my situation enough to help me. Any help is greatly appreciated.

    Thanks,
    James

    Code:
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    void lsd_radix_sort(unsigned int *, int);
    
    main(int argc, char *argv[]) {
            int i, nvals = 10000;
            unsigned int *array;
            if(argc > 1)
                    nvals = atoi(argv[1]);
            array = malloc(nvals * sizeof(unsigned int));
            for(i = 0; i < nvals; i++)
                    array[i] = rand();
            lsd_radix_sort(array, nvals);
            
    }
    
    
    
    #define	BITS	8	
    #define	RADIX	(1<<BITS)
    #define	DIGITS	(32/BITS)
    void lsd_radix_sort(unsigned int *array, int n) {
    	int i, j, k, d, shift;
    	int *bin[RADIX], n_in_bin[RADIX], size_bin[RADIX];
    	unsigned int v;
    
    /**insertion of least significant digit first code below ****/
    	
    
    }
    Last edited by wvu2005; 10-29-2005 at 02:44 PM.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    /insertion of least significant digit first code below ***** */
    ->
    Code:
    /* insertion of least significant digit first code below ***** */
    free() what you *alloc().
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    malloc.h? What compiler are you using?

    [edit]
    Try google.
    [/edit]
    Last edited by dwks; 10-29-2005 at 02:46 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    I use Cygwin (basically a UNIX emulator) as the compiler.

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    http://www.cygwin.com/faq/faq0.html#SEC118:
    Include stdlib.h instead of malloc.h.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Will do.

    Thanks.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Do you know much about radix sorting by the way DWKS? I'm pretty stumped, as you have probably already found out

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I know absolutely nothing about it. But someone here will.

    If you don't want to wait for that someone, see if google will help you.

    [edit]
    First hit on google: http://www.brpreiss.com/books/opus4/html/page518.html
    [/edit]

    [edit=2]
    I know it's in C++, but there is some sample code when you click on next:
    http://www.brpreiss.com/books/opus4/html/page519.html
    [/edit]
    Last edited by dwks; 10-29-2005 at 03:03 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Thanks for the reply, but I've seen both of those links. I always try to exhaust my resources before posting (i.e. Google searching, etc.). If anyone else can help, I'd be very appreciative.
    My main problem is finding any examples with a similar layout as the program I've posted.

    Thanks,
    James

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I'm pretty stumped, as you have probably already found out
    Then just looking at the code won't really be of much help to you. But if you insist: http://www.eternallyconfuzzled.com/t...ing.html#radix
    My best code is written with the delete key.

  11. #11
    Registered User
    Join Date
    Sep 2005
    Posts
    20

    What exactly is your question

    The only thing that I see you saying is that you don't know what you are trying to do. If you have a specific question about radix sort, what is it?

    I just finished implementing radix sort in C and in C#. I can attempt to explain the theory if that is what you are after. Do not ask me to give you my implementation, as that will not help you understand what you are trying to do.

    But like I said, if there is something specific that is stumping you, please feel free to post it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. My own itoa()
    By maxorator in forum C++ Programming
    Replies: 18
    Last Post: 10-15-2006, 11:49 AM
  3. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  4. Radix sorting
    By PJYelton in forum C++ Programming
    Replies: 2
    Last Post: 11-21-2002, 10:33 PM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM