1 Mar
2000
1 Mar
'00
12:10 p.m.
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(a)xenosoft.com
On 1 Mar 2000, Eric Smith wrote:
John Wilson <wilson(a)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.