Re: Help me with references

Oliver Wong wrote:

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

I understand this. If you know you are going to have fewer than 10 elements
why are you writing your own sorting routine? Use the API and keep the
code simple. If you aren't sure it is going to be fewer than 10 elements
you shouldn't be using bubble sort.

Then there is also the question of why you picked bubble sort from other
sorts that are O(n^2), like insertion sort, which is simpler and faster.

Again the preference should be to use the API where speed isn't a concern.


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

Right, but if you know your sort will be done in no time why are you
spending time optimizing it.

--
Kenneth P. Turvey <kt@xxxxxxxxxxxxxxxxxx>
.

Relevant Pages

  • 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: Sort Two Dimensioanl Array
    ... Does Chris' Bubble Sort work - works in 2003 Autotext. ... Sort the given array into order. ... Optional SortAscending As Boolean = True) ... Dim BubbleSort As Long ...
    (microsoft.public.word.vba.general)
  • Re: Bubble Sort in C
    ... although BubbleSort is ... most certainly not how normal people intuitively sort cards, ... quite likely to be the first *programmatical* sort they invent for ... it's a reasonable way to introduce the subject of sorting (with ...
    (comp.lang.c)
  • Re: Help me with references
    ... >> BubbleSort has a small constant. ... A clever sorting algorithm might use ... >> Mergesort of Quicksort if the size of the set is greater than 10 ... > you shouldn't be using bubble sort. ...
    (comp.lang.java.help)
  • Re: Whats the best language to learn...
    ... implement a sort routine which takes advantage of the element type being ... There's NO situation where bubblesort is more efficient than insertion ... bubblesort is *not* easier to understand than insertion sort (in fact ... but, yes, for most things quicksort is better, especially when one figures ...
    (comp.programming)