Re: Help me with references



Oliver Wong wrote:
> "Kenneth P. Turvey" <kt@xxxxxxxxxxxxxxxxxx> wrote in message
> news:erp6t2-etl.ln1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
>>If this is just a learning exercise then that's great, but if you really
>>want to sort something there really isn't ever a good use for bubble sort.
>>You should probably let Java do the sorting for you unless you have a
>>reason to use a specific algorithm. That algorithm will never be bubble
>>sort.
>
> Bubblesort is O(n^2) and Mergesort is O(n log(n)), but the O(n^2) in
> BubbleSort has a small constant.

Bigger than the n^2 coefficient of either straight selection
or straight insertion, though -- at least, on every machine I've
ever heard of. (Make that "every general-purpose computer."
Knuth shows that bubble sort and straight insertion are equivalent
in a network of comparators that can work in parallel; he also
cites Demuth's proof that bubble sort is optimal for a machine
with a cyclic "rotating drum" external memory and only enough
internal memory for one record.)

> A clever sorting algorithm might use
> Mergesort of Quicksort if the size of the set is greater than 10 elements,
> but use BubbleSort if it's smaller than 10 elements, for example.

It doesn't make sense to ride a jetliner from door to door;
agreed. It also doesn't make sense to ride to the airport on
a backhoe and come home on a bulldozer.

--
Eric.Sosman@xxxxxxx

.

Relevant Pages

  • Re: Selection-Sort in C
    ... bubble-sort or selection-sort? ... Bubble sort has these advantages. ... is a great sorting algorithm. ...
    (comp.lang.c)
  • Re: Selection-Sort in C
    ... I just look at the given Onotation and decide. ... algorithm known to Man? ... But bubble sort is surely the worst "basic" ...
    (comp.lang.c)
  • 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: Possible F77 Code Improvement ??
    ... In fact, it is probably the fastest sort, or at ... of bubble sort, heapsort and perhaps others. ... I can see how constructing the heap in this case requires only O ...
    (comp.lang.fortran)
  • Re: Which Algorithms are used most often ?
    ... told Bubble Sort is almost always a poor choice. ... Good algorithm books and courses are organized in a logical ... Let's analyze the sorting problem a bit: ...
    (comp.programming)