Re: Help me with references

Oliver Wong wrote:

> Knowing that you have fewer than 10 elements is a particularly good
> situation to write your own sorting algorithm, because you have knowledge
> about the problemspace that the general quicksort algorithm doesn't.
> Quicksort is optimized for large Ns. In the case where you not only know
> that your N is not large, but you additionally know the exact value of N,
> you can design an algorithm that is optimal for that specific N.

For almost any real problem you shouldn't bother optimizing code for sorting
10 elements. You should use the API and make your code clear and concise.

I'll give you that there are cases where comparisons take a long time and
you are in a tight loop where this is not the case. The odds that the
original poster was in this situation are nearly zero.


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

> I picked Bubblesort because your original post implied something along
> the lines of "it never makes sense to use bubblesort". I agree that a
> hybrid quicksort/insertion sort would be even better than a hybrid
> quicksort/bubblesort. I just wanted to point out that a hybrid
> quicksort/bubblesort is better than a pure quicksort.

Yes, but it still isn't the correct choice. There is always a better
choice. That is the point I was making to the OP.


>> Right, but if you know your sort will be done in no time why are you
>> spending time optimizing it.
>
> "No time" is dependent on the requirements of the environment. If
> you're
> workign with real time systems and you know for a fact that if the sort
> takes more than 10 milliseconds, for example, sick patients in hospital
> will not receive the proper injection of medication in time and die. Or
> aircrafts will collide with each other, possibily killing hundreds. 11
> milliseconds, which may seem like "no time" in most applications, isn't
> good enough. Optimizing it down to 8 milliseconds is worth it.

If you are in a tight loop or a critical section of code this is possible,
but again you shouldn't choose bubble sort for these few cases.

>> I am interested. I can't think of any situation in which bubble sort is
>> the
>> best choice for a sorting algorithm in a real machine.
>
> Depending on your definition of "best" (smallest worst case asymptotic
> running time?) and "real" (made by a big company such as Intel, AMD, IBM
> or Sun?), I'll probably agree with you. I could try to construct a
> situation where the desired output is not actually a sorted array, but an
> "almost sorted array" with some sort of rigorous definition of "almost
> sorted" such that BubbleSort might achieve this in (n^2+n)/4 comparisons
> whereas InsertionSort can only do it after the full (n^2+n)/2 in the worst
> case, but quite frankly I'm too lazy.

I suspect that even an "almost sorted array" could be produced more
efficiently than you can with bubble sort.


> Note that pragmatically, "best" may not always be synonymous with
> "technically best", in the sense that factors other than technology (e.g.
> business, politics, etc.) may affect what algorithms are used in a given
> environment.

Yes, but the sorting algorithm? I hope that there is nowhere that
management dictates the use of bubble sort. :-)

[Snip]
> The point of this anecdote is that you and I, as rational software
> developers, are not able to see an application of the BubbleSort algorithm
> where it is the optimal tool for a problem - but that does not
> nescessarily imply that there will *NEVER* (emphasizing this keyword) be a
> situation where it might make sense to use Bubblesort.

OK, if your manager mandates it, use bubble sort. :-)

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

Relevant Pages

  • Re: random access iterator
    ... The sorting algorithm isn't really relevant here. ... a random access iterator - not meant to teach bubble sort to readers... ...
    (microsoft.public.vc.language)
  • 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)
  • Re: HOW TO SORT???
    ... this so called bubble sort is usually the slowest possible ... be slower if the data are pre-sorted. ... algorithm quickest in all situation. ... a big problem with QuickSort. ...
    (comp.lang.pascal.borland)
  • Re: C Sharp sorting considered superior to C by an order of magnitude
    ... be sorted by algorithm A" is nonsense. ... using a bubble sort, etc. ... (about which sorting algorithm is used) ... but then good design usually does. ...
    (comp.programming)
  • Re: Test-Driven Development (was Re: Career? What languages to learn?)
    ... But I still have some reservations about TDD, ... > that make quicksort superior to bubble sort. ... TDD can force an algorithm to exist, ...
    (comp.programming)