Re: Sorting Algorythms

[Michael J. Mahon <mjmahon@aol.com>]

BLuRry <brendan.robert@gmail.com> wrote:
> On Tuesday, December 18, 2012 7:09:19 PM UTC-6, gid...@sasktel.net wrote:
>> I am sure everyone has dabbled in and programmed a sorting algorythm at
>> some time while playing on their Apple II computer.
>> 
>> 
>> 
>> What I would like to know is there any programs out there other than the
>> usual talked about ones or one they may have created themselves?
>> 
>> 
>> 
>> Bubble sort, Bi-bubble sort, Shell Metzner sort, Quick Sort, Field Sort,
>> Binary search sort, Heap sort, Interchange sort.
>> 
>> 
>> 
>> 
>> 
>> And what is the fastest sort anyone has come across.  Is Quicksort the fastest?
>> 
>> I re-engineered a sort that I came across, but I do not know the name of
>> it, that is about 35% faster than the quicksort.  With the added
>> advantage of leaving the original in tact as well as have multiple tag
>> alongs and it sorts numbers properly where the number 2 is less than 10.
>>  Most sorts will not sort numbers properly.
>> 
>> 
>> 
>> Rob
> 
> Academically speaking, QuickSort is the fastest general-purpose algorithm
> for moderate-to-large data sets.  For smaller sets (say, a few dozen)
> shell sort is almost equivalent in terms of speed.  If you're really
> tight on code space, nothing is smaller than bubble sort.  Even bubble
> sort is ok for small sets.
> 
> The wikipedia article on sorting algorithms does a great job comparing
> the pros and cons of each.  Really the worst you can do is implement BogoSort.

Read Knuth, volume 2: Sorting and Searching. 
It says just about all there is to say about the topic!

IIRC, there are 28 distinct sorting algorithms, and each is best for some
cases--except bubble sort, which is never optimal, but, ironically, is best
for tutorial purposes. ;-)

As a simple example, "pick-and-zot" is a tiny algorithm suitable for
sorting very short lists: find the minimum and process it, then set it to
"infinity". Repeat until the minimum element is infinity. 

Another extremely efficient algorithm if you have room for links is the
radix sort. Check it out. 

I've always liked the heapsort. If you keep a queue as a partially ordered
tree (a heap), then the next element to process is always at the root of
the tree, and, when the root is removed or an element is added, it only
requires log(n) comparisons for a heap of n elements--perfect for timer or
priority queues. 

-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon