Radix Sorting

[Foodbank]

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

#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

}

 

[Arctic Fidelity]

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

 

[Foodbank]

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

 

[Jordan Abel]

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.

 

[Foodbank]

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

 

[Christopher Benson-Manica]

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.

 

[Arctic Fidelity]

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

 

[Foodbank]

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