Re: Help me with references


"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. 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.

Consider sorting a set of size 40 for example. When you call quicksort,
it might break it into 2 sets of size 20 each. Call quicksort on each of
these, and you have 4 sets of size 10 each. It's actually faster to
bubblesort these sets of size 10 than to do further quicksorting. Once you
have 10 sorted sets, you can merge them back together using the normal
quicksort algorithm again.

- Oliver


.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... > best choice for a sorting algorithm in a real machine. ... Quicksort is optimized for large Ns. ... I picked Bubblesort because your original post implied something along ...
    (comp.lang.java.help)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... Quite was regarded Hoare's original Quicksort. ... Reversely sorted data ... Anyway QuickSort is very simple algorithm and it's complexity is precisely analized. ... further detailed retrospective of many QuickSort implementations as well as other sort algorithm will take too much time and space - wikipedia is starting point and give some interesting links for further analyze who is interested. ...
    (borland.public.delphi.language.basm)
  • Re: sorting algorithms
    ... >> Quicksort seems to have close this chapter and now nothing ... >> sorting algorithm was a competition like finding the longuest ... No sort does both on all input set ... You haven't defined what you mean by "efficient use of memory". ...
    (comp.programming)
  • Re: sorting
    ... The algorithm you choose depends a lot on the number of ... sort will be quick enough. ... Quicksort or another method. ... use Bubble sort algorithm which is ...
    (microsoft.public.excel.programming)