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/