From: mccullou@cae.wisc.edu (Mark McCullough)
Newsgroups: comp.lang.pascal
Subject: Re: Bubble Sort Routine
Date: 8 Oct 92 20:53:05 GMT
Organization: U of Wisconsin-Madison College of Engineering

In article <1992Oct6.115233.1534@cc.umontreal.ca> pigeons@JSP.UMontreal.CA (Pigeon Steven) writes:
>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.
Not to disagree with you, but log is base ten.  Since you are puttin all
the constants in, you should denote that the log is base 2, so use lg.
Minor point.
>
>>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.

What is being talked about is real time, not number of passes.  While
200,000 is quite large, I will say that anything under a few hundred
items to be sorted means that the differance in REAL time is not
enough to warrant looking up a quick sort.  Remember, programmers time is
also a factor in deciding the algorithm.
>
>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.

That second sort you described was not a bubble sort at all.  THe
bubble sort is really either a smart or a dumb sort.  In a dumb
sort, it is always n^2 comparisons.  This is because no exit
condition is added if no elements are flipped.  Fortunutelyn
, noone has talked about using that here.  The smart bubblesort
is what everyone is talking about here, with the flag to detect
if the list is sorted.

If you really want to have fun, do the following standard program.  Make
a program that will create an array of n random characters.  Print out
the array, then apply a sort.  Determine with time checks, how much time
the sort took.  (In the software.)  Keep the size of the array a constant
to make changing it easy.  Have say, a bubblesort, a quicksort, a shellsort,
an insertion sort, maybe even a few more.  Oh, and have all versions that
you can find of the bubblesort to compare them. (Or what people have been
calling a bubblesort recently.)  Start with a relatively small array, say
100 elements, then make it large, say 10,000 elements.  When I did this,
the quick sort took 7 seconds to sort.  I gave up on the bubblesort after
over 20 _minutes_.  (At 10,000 element array size).  When the array was
only 100 elements, the times were close enough (less than .4 seconds) that
it wasn't really worth much.  This was on a 7Mhz machine.  Try it on
your 486DX 50's to really have fun.  Then hit the turbo to slow it down and
see the difference.
:)M^2
Newsgroups: comp.lang.pascal