🚀 go-pugleaf

In article <BxIwoJ.Hr7@news.cso.uiuc.edu> jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
>
>   John Slagel (Me!) writes:
>
>>>>   Definately the quick sort.  Its even built into ANSI C specs, so it
>>>>   should be easy to implement.  Look up quicksort in your C manual. If
>>>>   I remember right, bubble sort works in O(n*n) and quicksort works in
>>>>   O(n*log n).
>>>>
>>>>   In other words, if you're sorting n objects, QuickSort takes "on the Order
>>>>   of" n*log n steps, while bubble sort takes "on the order of" n*n steps.
>>>>
>
>   Dave Roberts chokes at my stupidy:
> 
>>Ack!!! People, remember that bubble sort has a *worst* case time of
>>n!.  It can be quite fast if most things are sorted.
>
>>Dave Roberts
>>Advanced Micro Devices, Inc.
>>Network Products Division
>>david.roberts@amd.com
>
>   Ack!!! Me, John Slagel, who is a soon-to-be-interviewing senior
>   in C.S., gives up all hopes of getting a job with AMD :-)

Of course, I screwed up in writing that the worst case was n!, and not
n*n.  The second poster wrote that and I blindly repeated it without
thinking (USENET is terrible when used without discrimination).

Anyway, my point was that it's worst case behavior (which is n*n as
many, and John, pointed out) differs from its degenerate cases, which
can be O(n) if the data is sorted or nearly sorted.

My post was a knee jerk response that bubble sort is bad.  It's not.
Used wisely and carefully chosen, it's a beautiful thing.  I just hate
it when people automatically think that quicksort is the be-all
end-all sort of the millenium.

You can now safely interview since you correctly recalled that bubble
is n*n. :-)

Dave Roberts
david.roberts@amd.com