320.2! 301.5, 311.3, 65.4 - Page 173

Kamog · #**1721** October 10th, 2003, 07:53 AM

In school I wrote little programs to demonstrate bubble sort, insert sort, and quick sort, but I don't remember anything about radix sort. I do recall that quick sort was way faster than bubble sort.

Loser · #**1722** October 10th, 2003, 02:47 PM

The following link has been rated Sure, Why Not for mild content.

Loser · #**1723** October 10th, 2003, 05:02 PM

Gratuitous Double Post
major

Jack Simth · #**1724** October 10th, 2003, 07:01 PM

Quote:

Originally posted by Kamog:
In school I wrote little programs to demonstrate bubble sort, insert sort, and quick sort, but I don't remember anything about radix sort. I do recall that quick sort was way faster than bubble sort.

Which sort is best depends on a lot of things; bubble sort is O(n^2) (n: number of data elements to be sorted) for its worst case - the element that is supposed to be first is in the Last position. Its best case, an already sorted list, allows it to have a trapdoor and do the "sort" in O(n). Insertion and selection sort are also O(n^2) in the worst case. Quicksort is, in the average case, O(n*lg(n)), but O(n^2) in its worst case. Mergesort is always O(n*lg(n)), as is Heapsort. All of the above sorts are based on comparisons.

Radix sort is a different beast entierly - it isn't based on comparisons, it is based on indexing. You need to know certain things about the data you are sorting to make it work (type, bit significance order, data length), but given those, it does the sort in O(k*n) (k is the maximum data element length). How it works: You make a set of stacks based on how many chunks you want to cut your sort key up into, and label them by the value that particular chunk represents (e.g., if you were sorting byte arrays, you might go with 256 stacks, numbered 0-255 - you may want an additional stack if your list elements aren't all the same length - a 'beyond bounds' stack). You then take each list element, and put it on the stack representing that list element's least significant chunk. When you are finished stacking the list, you put those stacks back into the list in a particular order, and stack them from the list again, using the next least significant chunk of your sort key. You continue this process until you have gone through the entire sort key, and gather them up; the list will then be sorted. It is a totally bizzare sorting algorythm, but it works.