Re: Help me with references


"Kenneth P. Turvey" <kt@xxxxxxxxxxxxxxxxxx> wrote in message
news:hgg7t2-ur4.ln1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> 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.

I'm not trying to tell the OP that implementing bubble sort is a good
idea. All I was doing was pointing out that your statement "That algorithm
will never be bubble sort." is not nescessarily true in all situations.

If you're interested though, I can still answer the questions in your
post.

- Oliver


.

Relevant Pages

  • 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 elements, ... Then there is also the question of why you picked bubble sort from other ...
    (comp.lang.java.help)
  • Re: Use of nested loops.
    ... > Allan Bruce wrote: ... I have heard about bubble sort but have not yet ... It's the simplest form of bubblesort. ... adjacent out of order elements, will sort any given array order, ...
    (comp.lang.c)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... it turned out that my bubblesort was *slower* than ... distinct Integers, shuffled randomly. ...
    (comp.lang.java.help)
  • implementing sorting algorithm
    ... I have an assignment to make vhdl code for implementing bubble sort ... algorithm and I got problem with it, ... entity bubblesort is ... Sorry english is not my native language.. ...
    (comp.lang.vhdl)
  • Re: Performance mehrdimensionaler Arrays
    ... konkreten Implementation dieser Datenstrukturen und Algorithmen. ... Angenommen, Du möchtest was sortieren. ... Du kannst einen Bubblesort hinschreiben, ... Der Austausch eines Bubble- gegen einen Quicksort ...
    (de.comp.lang.delphi.misc)