Can it be done???

[swanley007]

Can the Radix/Bucket Sort be done using a linked list????

If so, How would one go about it...I am pretty bad and would ususally use a vector or array, but the program I am writing requires the linked list to be used.

[Glorfindel-RW]

The answer is easily googled... but here I go anyhoo.

For a radix sort you take the least significant digit...
IE: for the number 405, the 5.

You make a group of linked lists for each least significant digit encountered.

Now, combine these linked lists... (tail = head).

Now sort by the next significant digit and continue...

For example, consider the following set of data:
ABC, XYZ, BWZ, AAC, RLT, JBX, RDT, RDT, KLT, AEO, TLJ

On the first pass you'd get several linked lists (denoted by parenthesis)

(ABC, AAC) (TLJ) (AEO) (RLT, RDT, KLT) (JBX) (XYZ, BWZ)

Now combine....

ABC, AAC, TLJ, AEO, RLT, RDT, KLT, JBX, XYZ, BWZ

Now sort again by the next most significant digit...
(AAC) (ABC, JBX) (RDT) (AEO) (TLJ, RLT, KLT) (BWZ) (XYZ)

Combine...
AAC, ABC, JBX, RDT, AEO, TLJ, RLT, KLT, BWZ, XYZ

One last pass...
(AAC, ABC, AEO) (BWZ) (JBX) (KLT) (RDT, RLT) (TLJ) (XYZ)

Done!
AAC, ABC, AEO, BWZ, JBX, KLT, RDT, RLT, TLJ, XYZ

From:
http://www.nist.gov/dads/HTML/radixsort.html

[swanley007]

Yes I know how it works...but thank you for the info in the post as it may be helpful to others. The main question that I have is the specific code to deal with pointers/lists. All of the examples I have found deal with arrays or vectors...I can do these. As I mentioned before, I am bad with pointers/lists...so I was hoping that someone could show me how to do it using the pointers/lists.

[Ancient Dragon]

it can be done with linked lists, but first create an array of pointers to each of the nodes in the linked list, then bump the sort algorithm against that array of pointers. In the swap routines you have to be careful to not exchange the pointers or destroy the next and previous pointers of the nodes. The actual data has to be moved around, not any of the pointers (unless the data itself is a pointer to some object). I suppose with large amounts of data in each node it might be well worth time spent to find an algorithm that swaps the node pointers, being careful to also set the next/previous pointers correctly.