Posts: 357
Threads: 118
Joined: Oct 2004
My comp sci professor mentioned that a Radix sort was of O(n**2) and I already knew that Quicksort was O(n lg n) -> O(n**2). But last year I wrote a program that ran multiple types of sorts against each other and the Radix sort always beat out the Quicksort. I've read up and seen different people have different breakdowns of the radix sort. I've even seen someone break it down to a linear function. My analysis comes to O(n * digits). What is everyone elses experience with these two sort styles?
f you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows.
Posts: 3
Threads: 0
Joined: Sep 2005
Your assessment of O(n · digits) is mostly correct for Radix sort. Radix is considered to operate in O(n · k) time, where k is the average key length. When both key length and number of items is large, Radix performance degrades to O(n · log n), which is the same as Quicksort's average time. The main disadvantage of Radix is that it typically requires O(n) additional memory space, so for large lists or restricted memory situations it is not always a suitable replacement for an in-place algorithm such as Quicksort.
Another consideration of Radix vs. Quicksort is whether stability is required. Stable sorting algorithms keep the relative order of records when comparing equal keys. So if there are two records, A and B, with equal keys, with A coming before B in the original list, A will still come before B in the sorted list. With unstable sorting algorithms such as Quicksort, after the list is sorted A may or may no longer come before B. In some cases, this could cause undesirable results. Unstable sorting algorithms can be implemented with special cases in order to operate as stable algorithms, but of course that affects performance.
Consider the following list of hexadecimal values, given as (X, Y):
(FF, 00) (00, 00) (00, FF)
If you were to sort by X in ascending order, a stable sort would always produce:
(00, 00) (00, FF) (FF, 00)
An unstable sort could sometimes produce:
(00, FF) (00, 00) (FF, 00)
Two different results, same sorting criteria. Depending on what is required from the data, such differences could be significant.
So, it basically boils down to what you need from a sorting algorithm. Speed, memory usage, and stability need to be considered on a case by case basis. Fortunately, with Freebasic making it easy to address large amounts of memory, it's now possible to consider Radix in many instances when for QB the Quicksort would be better suited.
Posts: 1,956
Threads: 65
Joined: Jun 2003
Another problem with unstable sorts like Quicksort is that they destroy any original sequence that the file might have.
Example: Let's say we have an employee file which is already maintained in employee number sequence. If we do a Quicksort on this file by last name, the employee number sequence is lost. That is, if I look at the M's in the file, these M records are no longer in employee number suquence within the last name, which they would automatically be when sorted with a stable sort. I now have to be aware of this when using Quicksort, and sort on the last name and the employee number.
*****
