Robert Dewar (dewar@cs.nyu.edu) wrote:
: (slightly corrected version, I noticed a minor typo in the first version,
: which I canceled).

: Richard O'Keefe says

:   "Now the funny thing here is that Robert Dewar wrote
:   >you will almost certainly find you require more overhead
:   [for insertion sort than bubble sort]
:   >because of the two nested loops.
:   But both versions of bubble sort have two nested loops as well!"

: You missed the point. In the bubble sort, the outer loop is executed only
: once for a sorted list. For your insertion sort, the outer loop runs a full
: number of times. Your insertion sort has 2*N loop termination tests, while
: a properly written bubble sort has N loop termination tests.

But on a sorted list the bubble sort the inner loop also involves an extra
comparison test, which for the insertion sort is part of the second 
termination test. So it is more complex than you make out. Does it cost more to
compare two elements than test a loop counter? For many data items it is much
more. (Consider for example the speed of strcmp vs '>' on ints.)

If you need to do a sort at all then at least some of the time you are trying
to sort an unsorted list. Unless this is very rare then the cost of sorting an
already sorted list is not a very good guide to actual behaviour in practice. 

Once you get one element out of place you have to take into account the cost 
of moving elements too. This could be expensive and bubble sorts can do a lot
more than insertion sorts (depending on the coding). So to decide the best sort
you may have to benchmark several sorts and several codings and decide on how
to trade of speeding special cases vs code complexity.

: I do not know any way to write the insertion sort so that it has only N
: loop termination tests, certainly your example has 2*N tests.

: Here is a simple example of bubble sort the way I would code it

:    procedure Sort (N : Positive; Exch : Exch_Procedure; Lt : Lt_Function) is
:       Switched : Boolean;
:    begin
:       loop
:          Switched := False;

:          for J in 1 .. N - 1 loop

Note that for each iteration of the outer loop one element at least will
have bubbled to the correct position, so you can decrease the range of
the inner loop by one for each itteration of the outer loop. This makes
the code more complex but may double the speed on unsorted input data.

--
Stephen Baynes                              baynes@ukpsshp1.serigate.philips.nl
Philips Semiconductors Ltd
Southampton                                 My views are my own.
United Kingdom
 Are you using ISO8859-1? Do you see � as copyright, � as division and � as 1/2?