On Thu, 27 Oct 2005 08:48:41 -0400, Foodbank <v8********@yahoo.com> 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/ 
