Re: Possible F77 Code Improvement ??

In article <gp7tc3$b2u$1@xxxxxxxxxxxxxxxxxxxxxxxx>, nmm1@xxxxxxxxx
wrote:

In article <ron-shepard-6F546C.00545411032009@xxxxxxxxxxxxxxxxxx>,
Ron Shepard <ron-shepard@xxxxxxxxxxxxxxxxxx> wrote:

If the data are almost in the final order, then bubble/insertion
sort is only O(N). In fact, it is probably the fastest sort, or at
least among the fastest, in this special case.

That's just a search. It can be regarded as an extreme case of any
of bubble sort, heapsort and perhaps others.

I can see how constructing the heap in this case requires only O(N)
comparisons, and no or few interchanges, but the second part of the
heapsort requires O(N*Log(N)) effort regardless of the values in the
heap. Right?

But the bubble/insertion sort would basically consist of the N
comparisons to verify the order, along with a few interchanges to
fix the few elements out of order, and that would be the end.


Also, if you want to find a few of the largest (or smallest) values
from a large array, then (if I remember correctly) a modified bubble
sort is the best algorithm.

Actually, it's a modified heapsort! If I recall, the modification
is equivalent for a modified buggle-sort for very small extractions
(say, up to 3 or 4). But it's a long time since I looked at that.

Say you want to find the largest 10 elements in an array 10^6 long.
With the bubble sort, you scan through the elements in the array
once and insert them into the 10-element target. But with a
heapsort, you still have to set up the heap, which requires
O(N*log(N)) in the general case. I can see how the second step
where you extract 10 elements from the heap is truncated, but the
first step would require the full effort.

There is another interesting case where sorting is reliably O(N).
If the data are from a known distribution, there are two sorts that
use only O(N) comparisons (with probability one).

Do you mean the situation where you are merging two sorted lists?
Yes, that is O(N) effort.

Both of those statements are very true. I don't often use it, but
the reasons are due to my personal history (i.e. pure bias!)

I admit some personal bias towards heapsort too. First I like its
simplicity, which as I mentioned before often allows you to work
directly from the heap rather than from the fully sorted data. For
example, it is straightforward to add new elements to a heap as they
become available, so if you can work directly from the heap data
structure in your application, you can avoid some redundant effort
associated with resorting your data. Second, heapsort was easy to
implement in f77. It did not require complicated memory management,
or recursion, or pointers, or allocation of dynamic work arrays, and
so on. Those language limitations no longer apply to f90 and later,
but that was one reason I liked it.

[...]
and tuning heapsort for extreme architectures defeats most people.

Yes, this is a problem that (I think) is inherent in the heap data
structure itself.

$.02 -Ron Shepard
.

Relevant Pages

  • Re: Possible F77 Code Improvement ??
    ... In fact, it is probably the fastest sort, or at ... of bubble sort, heapsort and perhaps others. ... tracking down the bug is not easy at all. ...
    (comp.lang.fortran)
  • Re: Mergesort Vs Quicksort
    ... is in a heap* order w.r.t. a flipped comparison function (you sort ... Yeah, I am pretty sure this is the case. ... hybrid sort rather than a pure merge sort. ... list is always in a heap compliant state. ...
    (comp.programming)
  • Re: Returning Median Value
    ... That you are sorting singles does not make a great difference, the relative performance of the sorts in relation to each other remains the same and the absolute performance may be a little bit slower because comparing singles costs a little bit more than comparing longs. ... Max stack depth was set to 60 (which should be sufficient for up to 1 million elements to be sorted without resorting to insertion or heap sort in amlost all cases). ... Now if you can bear 4 ms for sorting 1000 items using bubble sort, ... Also the relative performance will change too, when the distribution of the items to be sorted changes. ...
    (microsoft.public.vb.general.discussion)
  • Re: A "valid" Bubble sort algorithm?
    ... > bubble sort algorithm given by program 6.4 in Algorithms in C by Robert ... The BubbleModLong sub below is from an unknown source and is ... > Dim i As Long ...
    (comp.programming)
  • Re: Compost question
    ... your sort of heap is a Bad Idea. ... if a Web site refers to 'green' and 'brown' material, ... |> about six holes right near the bottom and only small ...
    (uk.rec.gardening)