Date:	Mon, 23 Feb 1998 05:18:10 -0500 (EST)
Message-Id:	<199802231018.FAA18007@p2.acadia.net>
To:	broadview AT earthlink DOT net
Subject:	Re: Sorting Algorythums
Cc:	djgpp AT delorie DOT com
References:	<34F113BA DOT 203AD4E9 AT earthlink DOT net>
in-reply-to:	<34F113BA.203AD4E9@earthlink.net>
From:	swarnerx3 AT acadia DOT net (Scott Warner)
MIME-Version:	1.0

In message <34F113BA DOT 203AD4E9 AT earthlink DOT net>, "STEVEN S. FALLS" <broadview AT earthlink DOT net> wrote:
>     What is the best sorting algorythm and what is it. I mean, how would
> one program the algrothym?
>             Thanks,
>                         -Ardy
>
>

Ardy,

Well, I'm not expert on sorting techniques, but maybe this will help --

There are many sort algorithms.  Generally, they involve systematically comparing and swapping members of the set until all the members are sorted according to criteria (such as alphabetical).  The most inefficient way is to compare the first element against every element, then the second element against every element except the first, and so on, but it works.  This (I believe) is also called the bubble sort, which has n*(n-1) ifs.  The idea is, fewer passes, fewer compares & swaps, more efficient sorts.

Some ideas for you:

1.  Loop through the array, compare each element with the following element.
2.  If the two elements are out of order, swap them.
3.  Repeat until (2) is no longer performed.

This is the bubble sort -- very inefficient, but it works.  It may even work fast enough for some applications, but there are always better sorts.

The shell sort is similar, but it compares elements that are far apart:

1.  Divide the list into 2 equal partitions.
2.  Compare each element of the first partition with the corresponding element of the second partition and swap if necessary.
3.  Divide each partition into 2 partitions and repeat step 2.
4.  Continue until partition size = 0.

This is much more efficient than the bubble sort, although it is just slightly changed.  Indeed, the last pass is a bubble sort.  Point is is takes only a few more lines of code and is probably at least twice as fast.

The quick sort is part of some C implementations, although it isn't ANSI afaik.  There are many, many others, such as the shell sort and comb sort.  All of these are much more efficient than the bubble sort, and not that much more difficult to program.  You might try ftp://ftp.cdrom.com/pub/algorithms for examples.  It's a field worthy of study in its own right that I have only scratched at, but you may find something useful there.


Hope it helps,

Scott

- Raw text -