Radix Sorting

Discussion in 'C Programming' started by Foodbank, Oct 26, 2005.

  1. Foodbank

    Foodbank Guest

    Hi everyone. I'm having trouble with this radix sorting program. I've
    gotten some of it coded except for the actual sorting :( The book I'm
    teaching myself with (Data Structures Using C and C++) just doesn't
    explain things good at all and the tutorials I've viewed don't really
    explain least significant digit first sorting or show examples, which
    would be most helpful. I've commented the section where I know that
    the iteration of the least significant digit sorting goes. Any input
    is greatly appreciated.

    Thanks,
    James


    Code:
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    int check_order(unsigned int *, int);
    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] = random();
    	lsd_radix_sort(array, nvals);
    	if(i = check_order(array, nvals))
    		printf("%d misorderings\n", i);
    	else
    		printf("array is in order\n");
    }
    
    int check_order(unsigned int *ip, int n) {
    	int i, nrev = 0;
    	for(i = 1; i < n; i++)
    		if(ip[i-1] > ip[i])
    			nrev++;
    	return(nrev);
    }
    
    #define	BITS	8	/* specify the radix by number of bits */
    #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;
    
    //least significant digit first radix sort
    
    }
     
    Foodbank, Oct 26, 2005
    #1
    1. Advertising

  2. On Wed, 26 Oct 2005 10:12:31 -0400, Foodbank <> wrote:

    > Hi everyone. I'm having trouble with this radix sorting program. I've
    > gotten some of it coded except for the actual sorting The book I'm
    > teaching myself with (Data Structures Using C and C++) just doesn't
    > explain things good at all and the tutorials I've viewed don't really
    > explain least significant digit first sorting or show examples, which
    > would be most helpful.


    I am sorry that I don't have more helpful advice to give you, but I did a
    Radix sort quite successfully as one of my first takes into Scheme. I
    unfortunately only have that as an example of how it might be done. If you
    don't mind, you might check that out for some ideas about how the logic
    and such might flow, and since the concept is fairly simple, you should be
    able to put the code into your own words quite easily.

    http://www.aaronhsu.com/progport.html -> Page w/ Description
    http://www.aaronhsu.com/src/radix-sort.zip -> Source

    The functions are all pretty straightforward, and it will give you a
    simple idea of how the sorting is done. From what I understand, a C type
    Radix sort is easily and most effeciently executed by just shifting
    pointers or something like that. I was thinking of actually doing the C
    version of my Radix sort just a little while ago, and I might just do it
    now.

    - Arctic

    --
    Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
     
    Arctic Fidelity, Oct 26, 2005
    #2
    1. Advertising

  3. Foodbank

    Foodbank Guest

    Thanks for the help Arctic, but your files are not really viewable the
    way that they are presented. When opened by an editor, the code is one
    or two really long horizontal lines. When you zipped it, that must
    have not kep the original formatting of the file. If possible, could
    you post a text file or similar so that I can actually read and follow
    your code?

    Thanks,
    James
     
    Foodbank, Oct 27, 2005
    #3
  4. Foodbank

    Jordan Abel Guest

    On 2005-10-27, Foodbank <> wrote:
    > Thanks for the help Arctic, but your files are not really viewable
    > the way that they are presented. When opened by an editor, the
    > code is one or two really long horizontal lines. When you zipped
    > it, that must have not kep the original formatting of the file.
    > If possible, could you post a text file or similar so that I can
    > actually read and follow your code?
    >
    > Thanks,
    > James


    Most likely you are on windows and he is on a unix-like platform -
    select all text and paste into wordpad, or open the file in wordpad
    in the first place.
     
    Jordan Abel, Oct 27, 2005
    #4
  5. Foodbank

    Foodbank Guest

    That worked Jordan. Thanks for the advice.

    As for the program that you provided Arctic. I appreciate the effort,
    but I think that code is a little out of my league. I'm trying to do
    the most basic of radix sorting and it was hard for me to understand
    that code. If anyone else has any input regarding my code, I'd greatly
    appreciate it (beginner radix sorting input that is :) )

    James
     
    Foodbank, Oct 27, 2005
    #5
  6. Foodbank <> wrote:

    > As for the program that you provided Arctic. I appreciate the effort,
    > but I think that code is a little out of my league. I'm trying to do
    > the most basic of radix sorting and it was hard for me to understand
    > that code. If anyone else has any input regarding my code, I'd greatly
    > appreciate it (beginner radix sorting input that is :) )


    It is proper Usenet etiquette to include the relevant portions of the text
    you are replying to. To do this using Google groups, please follow the
    instructions below, penned by Keith Thompson:

    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Oct 27, 2005
    #6
  7. On Thu, 27 Oct 2005 08:48:41 -0400, Foodbank <> wrote:

    > As for the program that you provided Arctic. I appreciate the effort,
    > but I think that code is a little out of my league. I'm trying to do
    > the most basic of radix sorting and it was hard for me to understand
    > that code. If anyone else has any input regarding my code, I'd greatly
    > appreciate it (beginner radix sorting input that is )


    The only file you really ought to concern yourself with then, is the
    rdx_algor.scm file. It's less than 50 lines long. I don't think you can
    get more simple than that, not by much anyways.

    The basic idea is:

    Get an unsorted list (it's a linked list in my program) and the number of
    digits in each number.

    Create bins, the number of which is equal to the base of the numbers you
    are sorting, that is, 10 bins for a decimal system, 2 bins for binary, etc.

    Read the first number from the list, and the appropriate digit from that
    number, and place the digit into the according bin.

    Repeat with all the numbers in the list, and then recombin the elements
    into a list starting with the lowest bin (0) if you are doing lowest to
    highest, or vice versa if you are doing highest to lowest.

    Repeat this with each digit in the numbers.

    My program is one main recursive loop, and one other loop. Two loops in
    total:

    main : <unsorted list> <digits> -> <list>

    The way the main loop works is by decrementing the digit (like a counter)
    until it is zero, at which point it returns the fully sorted list. The
    reason this happens is because the divide function uses this digit to
    reference a point in the number. So if we had ten digits in each number,
    the first call to divide would have 10 as the value for digits. And
    calling the 10th element of a string would be the least significant digit
    if the string were a number. It's a pretty simple recursive loop.

    All the recombine function does is take a two dimensional array of size 10
    by whatever (linked lists) and append all the lists together into one.

    All the divide function does, really, is loop through the list, and look
    at the digit referenced by its second argument, and append that number to
    the appropriate bin list. That's the hardest loop, and the logic might go
    something like:

    divide : <list> <digit> -> <2d array>

    create an array of 10 digits, each element being a list of numbers (2d
    array)
    read the first item from list
    read the element referenced by <digit>
    switch (element)
    case 0: append array[0] with num
    case 1: append array[1] with num
    case 2: etc.
    etc.
    repeat procedure on next item until no more items in list
    return the 2d array to be recombined by another function.

    So really the logic isn't too hard. Perhaps what is throwing you is that I
    used recursion and functional programming style, which doesn't always map
    directly to C. BUt what fun would it be if I gave you a working C program
    of the same? I am sure you can find some of those around, but I doubt
    that's what you want to do. This is a learning exercise, no?

    Really, a radix sort is a radix sort, the logic is all the same.
    Understand that there are really only two logical loops happening. One is
    controlling which digit of the numbers you are working on, the other is
    reading that digit and putting the numbers into the appropriate slots.
    There are other ways to do it, I am sure, but I find that easiest.

    I hope that helps a bit.

    - Arctic

    --
    Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
     
    Arctic Fidelity, Oct 28, 2005
    #7
  8. Foodbank

    Foodbank Guest

    I really appreciate your help Arctic. As for a working program, this
    is a learning exercise, but I think I would be so much better off with
    something that I could run and follow the steps through with printfs.
    If you don't mind, could you possibly post an example that you have?

    Thanks,
    James
     
    Foodbank, Oct 28, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. senthil
    Replies:
    3
    Views:
    1,937
    prabinthomaskottayil
    Nov 25, 2011
  2. Kevin Doyle

    _ultoa radix??

    Kevin Doyle, Sep 8, 2003, in forum: C++
    Replies:
    18
    Views:
    994
    Kevin Goodsell
    Sep 9, 2003
  3. Foodbank

    Radix Sort Help

    Foodbank, Oct 29, 2005, in forum: C Programming
    Replies:
    2
    Views:
    498
    Thad Smith
    Oct 30, 2005
  4. Foodbank

    Radix Tree

    Foodbank, Nov 7, 2005, in forum: C Programming
    Replies:
    1
    Views:
    1,441
    Michael Mair
    Nov 7, 2005
  5. Tarique

    Radix Sort

    Tarique, Feb 1, 2008, in forum: C Programming
    Replies:
    3
    Views:
    731
    Tarique
    Feb 1, 2008
Loading...

Share This Page