Can it be done???

This is a discussion on Can it be done??? within the C++ Programming forums, part of the General Programming Boards category; Can the Radix/Bucket Sort be done using a linked list???? If so, How would one go about it...I am pretty ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    85

    Can it be done???

    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.

  2. #2
    CS Major Glorfindel-RW's Avatar
    Join Date
    Nov 2005
    Posts
    5
    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

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    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.

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    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.
    Last edited by Ancient Dragon; 11-04-2005 at 04:00 PM.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21