From: pigeons@JSP.UMontreal.CA (Pigeon Steven)
Newsgroups: comp.lang.pascal
Subject: Re: Bubble Sort Routine
Date: 6 Oct 92 11:52:33 GMT
Organization: Universite de Montreal

In article <NMOUAWAD.92Oct5153412@neumann.waterloo.edu> nmouawad@waterloo.edu (Naji Mouawad) writes:
>Buble sort is far from being a "dead sorting technique". When
>analyzing the complexity of sorting one should consider three factors:
>that of the hidden constant in the "big oh" expression, that of the
>treshhold above which a faster sorting routine may be desirable and
>that of the expected running time as a function of the probabilistic
>distribution of the data.

OK. Let's talk about the O (big O) notation. Bubble sort, as most of
us knows it, has a best case of n (already sorted), which give a lower
bound of O(n). But, it also have a worst/average case of 1/2(n^2+n), 
which give an upper bound of O((1/2)(n^2+n)), considered O(n^2). Quicksort 
has a average-performance of O(n*log(2)n), and a absolute worst case (which 
I admit, I never succeded in producing it!?!) of O(n^2), which is best
than bubble sort.

>For any thing below 20k bubble sort is superior to Quicksort.
Drop the k, please.

>For any thing under 200k bubble sort will perform almost as well (we
>are talking in seconds here) as Quicksort on a randomely distributed
>data.

Come on. You must be joking. Or, your are calling bubble sort some sort
of sort that is not a bubble sort. For 200k, bubble sort will have to
perform (1/2)(200k^2+200k) passes: i.e. = (1/2)(4.194e10+204800)..=
2.097e10 operations. Quicksort, with average of nlogn would give 
3613462 (or 3.6e6). Note that bubble sort' average time is also its
worst.

Here's why: Quick sort, in it's absolute worst case, will create parti-
tions so that one is 1 element long, and the other (n-1) element long.
But, it should be possible to go on like that, and to reach the case of
(n-1)+(n-2)+...(n-(n-1)+1 operation, that is 1/2((n-1)^2+(n-1)), but the
algorithm I use (and most of quicksort-ers use), will make so that the
probability of such and occurence diminishes by choosing a pseudo-median
pivot, thus reducing the partitions toward best-case (and almost average
case) of both partition beeing about (n/2) elements long. By dividing by
2 each time, we have the case of n*log(2)n, which is not so bad, and al-
most the theorical lower bound for ALL sorts.

The bubble sort as I know it comes in two fashion: the very basic bubble
sort, and the "inverse insertion sort" (In french: "tri par insertion
renversee"). The first version starts at the bottom of the array to be
sorted, and verifies if the first element is bigger than the second 
element, and if it is so, it swaps. Then, it compares the second to the
third, and if the second is bigger, it swaps. So to the end of the array
and the processes repeats until no more swaps occurs. That gives n^2 op-
erations. The other, compares the first element to all others, so that it
can be made sure that it is lower or equal to all others. First pass require
(n-1) compares and/or swaps. The second, (n-2). Total: (1/2)((n-1)^2+(n-i)).

Or, maybe what you call bubble sort is no bubble sort at all.

>For files above 200k things start to matter.
>
>naji.
>
>--
>     -------------------------------------------------------------------
>    | Naji Mouawad  |          nmouawad@watmath.waterloo.edu            |
>    |  University   |---------------------------------------------------|
>    | Of Waterloo   |   "The Stranger in us is our most familiar Self"  |
>     -------------------------------------------------------------------


-- 
 _ ___  __       __ _  | Steven Pigeon
(_  |  (__ \  / (__ |\ | (a.k.a)
__) |  (__  \/  (__ | \| pigeons@JSP.UMONTREAL.CA
==Computer Science & Operation Research, Universite de Montreal==
Newsgroups: comp.lang.pascal