Re: Low-level vs. High-level programming (was My First Computer)

[pausch@saaf.se (Paul Schlyter)]

In article <3EF29823.BC1075DC@ev1.net>,
Charles Richmond  <richmond@ev1.net> wrote:
 
> Kevin Lawton wrote:
> 
>>        [snip...]            [snip...]            [snip...]
>> 
>> I'm not too sure how the quicksort in Java works internally. It would not be
>> exactly brilliant programming practise to use a bubblesort in C to sort a
>> very large number of items. In fact, I don't think it a particularly great
>> idea to use a bubblesort to sort large numbers of items in any language. A
>> bubblesort is more suited to working on reasonably small numbers of items.
> 
> Yes, a bubblesort is suited to working on reasonably small numbers
> of items. And a bubblesort is *stable*, meaning that if two records
> have the same value for the sort key, those records will *not* be
> exchanged. This is important in secondary sorts. 
> 
> But bubblesort *can* be suitable for sorting large numbers of
> items, *if* you can have some way to guarantee that the list of
> items is already *almost* sorted. With only one or two records
> out of order in thousand, you might use a bubblesort effectively.
 
One way to deal with this is to do two rounds of bubble sort, in
opposite directions, and then check if the data is sorted (by doing a
third round of bubble sort; of there are no swaps, the data is
sorted), If the data isn't sorted after this, switch to another
sorting algorithm.
 
-- 
----------------------------------------------------------------
Paul Schlyter,  Grev Turegatan 40,  SE-114 38 Stockholm,  SWEDEN
e-mail:  pausch at stockholm dot bostream dot se
WWW:     http://www.stjarnhimlen.se/
         http://home.tiscali.se/pausch/