Lately I keep running into people who are using "SORT" programs when that
isn't even what is called for.
1) Large sorted data file. Additional records are appended to the file.
Then the file is "SORTED" again. All of the "good" sorts being mentioned
take the same amount of time to sort the file regardless of whether the
content is random, or almost in order. For this particular example,
therefore, they take significantly LONGER than a properly written Bubble
sort (needs to be written to make each pass going down)
for (j=n-1; j>0; j--) . . .
2) Partial display. A search engine finds a LARGE N of results. It then
proceeds to SORT it using some "sophisticated" SORT program. After all of
the records are sorted, it then shows the first screenful (maybe a dozen
records) N does NOT have to be very large for the SORT of the entire set
to take longer than would a Bubble sort (again with each pass going down),
since 12 passes of the Bubble sort will produce those first 12 records,
and the remainder of the sort can continue while the reader is dealing
with those first 12.
For truly random data, the Bubble sort is indeed normally the wrong choice
by a significant margin. But the data is not always random, and the
display requirements do not always call for completion of the entire
sort as the relevant point to time.
Q: For data that is partially in order, but not necessarily appended new
records (for example resorting a file that has had excessive manual
insertions, etc.) does anyone know of an algorithm that is more efficient
at taking advantage of existing order than a Shaker sort (Bubble sort with
alternating direction for each pass)?
--
Grumpy Ol' Fred cisin_at_xenosoft.com
On 1 Mar 2000, Eric Smith wrote:
> John Wilson <wilson_at_dbit.dbit.com> wrote:
> > I remember one of Jerry Pournelle's more lucid rants in Byte, ages ago, where
> > he questions the whole point of the Bubble Sort to begin with. Not only
> > is it an absolutely horrible algorithm, it's not even immediately obvious
> > how it works!
>
> I'd have to disagree with him about the obviousness. It seems perfectly
> obvious to me that if you keep swapping out-of-order elements long enough,
> eventually a list will be sorted. It also seems obvious that if you do
> this systematically by scanning the list from one end to the other
> repeatedly, that it can take no more than n-1 passes, the time it would take
> an element to move from one end of the list to the other.
>
> The only other in-place sort that seems more obvious to me is:
>
> for (i = 0; i < (n-1); i++)
> for (j = (i+1); j < n; j++)
> if (a [j] < a [i])
> swap (& a [j], & a [i]);
>
> which has the disadvantage over bubble sort of doing more swaps.
>
> A Shell-Metzner (sp?) sort is substantially more efficient but also much
> less obvious.
Received on Wed Mar 01 2000 - 20:10:20 GMT