Thread: radix sort and radix exchange sort.

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    7

    Question radix sort and radix exchange sort.

    Hi, I've been searching the net for info on the radix exchange sort algorithm, inparticular, its order of complexity. Its got a little confusing for me as I found a lot of stuff on radix sort. Is there a difference in the way they operate as from what I can gather, radix exchange swaps 1s and 0s in binary from the top and bottom of the list of numbers and radix sort uses a partition value and sub arrays similar to quicksort.
    I also got confused with the order of complexity. Radix sort has O(NlogN) complexity, which I can understand as it uses recursion and is approx. halved, but radix exchange was said to be O(bN) where b is the number of bits. I am not sure how this works as when the MSB column is completed, then two numbers are sorted and can be ignored and so on until tht sort is complete.
    Sorry if thats not clear, but thanks if anyone can help me with this.

  2. #2
    Registered User
    Join Date
    Jul 2003
    Posts
    7

    Thumbs up

    Thanks Salem. Much appreciated.
    Could someone let me know whether I was right about the differences between radix sort and radix exchange.
    Cheers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. MSD vs. LSD radix sort
    By Micko in forum C Programming
    Replies: 1
    Last Post: 11-03-2005, 02:41 PM
  2. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  3. Radix Sort, Strings, and Linked Lists
    By dark paladin in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 03:24 PM
  4. Radix Sort question
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 01-06-2003, 06:58 AM
  5. Linked list & radix sort question, please help!
    By Lior in forum C Programming
    Replies: 5
    Last Post: 09-02-2002, 07:25 PM