Thread: Radix Sort question

  1. #1
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343

    Radix Sort question

    Hello everbody,

    didnīt really know where to post this thread but I think here would be the best place (for me ). Iīve been trying to figurate out when to implement Radix Sort. From my knowledge this is a very powerful algorithm that works only with numbers (I think???) and I canīt really se any downside with it except maybe for the memory consumtion with large numbers? Isnīt this the ultimate sorting algorithm (for numbers)???

    My simple qustion is: When should I use Radix Sort?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Isnīt this the ultimate sorting algorithm (for numbers)???
    No, I believe Quicksort has that title for the time being. And Radix sorts work with binary numbers, they can be used for non-numerical data as well.

    >When should I use Radix Sort?
    When it works best for your needs. Just like any sorting algorithm you choose the best combination of speed, stability, simplicty, and potential worst case for your particular problem.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    And Radix sorts work with binary numbers, they can be used for non-numerical data as well.
    Depends on what you use for the stable sort for each digit.
    If you use counting sort then I don't see any *easy* way to get that sort to use non-numerical data.

    I canīt really se any downside with it except maybe for the memory consumtion with large numbers? Isnīt this the ultimate sorting algorithm (for numbers)???
    There is alot of copying if you use counting sort also.

  4. #4
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    prelude, not sure what you would use as criteria for "ultimate sort algorithm" but radix is faster than quick sort (for the cases it can be used) by a substantial margin. Where I can use radix I do.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    prelude, not sure what you would use as criteria for "ultimate sort algorithm" but radix is faster than quick sort (for the cases it can be used) by a substantial margin. Where I can use radix I do.
    Plain quicksort, maybe, but I doubt, on average, you can get faster then quicksort with the following provisions
    1. removing one level of recursion
    2. insertion sort for small cases.

    Radix sort can be made to run in O(n) worse case, much faster
    than O(n^2) quicksort's worse case but the extra copying slows
    it down.

  6. #6
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    copying isn't much of a factor if you use pointers. Radix is faster. Quicksort has only the advantage of being more generic and usable on more types.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I need help to compile this code...
    By wise_ron in forum C Programming
    Replies: 17
    Last Post: 05-07-2006, 12:22 PM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. cin Help...Sort of a noob Question?
    By Krak in forum C++ Programming
    Replies: 9
    Last Post: 01-26-2003, 01:23 PM
  4. question about Quick Sort
    By Liberty4all in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2002, 10:38 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM