From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.1 required=5.0 tests=BAYES_00, PP_MIME_FAKE_ASCII_TEXT autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: baynes@ukpsshp1.serigate.philips.nl (Stephen Baynes) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/19 Message-ID: X-Deja-AN: 175098329 sender: news@ukpsshp1.serigate.philips.nl (account for localnews) references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> followup-to: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada organization: Philips Semiconductors, Southampton, UK newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-19T00:00:00+00:00 List-Id: Robert Dewar (dewar@cs.nyu.edu) wrote: : Stephen says : Why do people try and teach students Bubblesort? It may be an interlectually : interesting exercise but it is of no use. An insertion sort is simpler and at : least as fast as a bubble sort. For many practical programing problems an : insertion sort is a sensible solution, it is very compact and for small : d atasets as fast as anything (Many quicksort implementations switch to : insertion sort for less than about 7 items). The number of times I have : had to redirect graduates who have tried to write a small sort using : Bubblesort (because it was the simplest sort they were taught) or Quicksort : (because they have been taught it is faster in all cases). : The one advantage of bubble sort is that it is close to optimal on sorted : or nearly sorted arrays. You have to be very careful how you write insertion : sort not to require more compares in the fully sorted case, and you will : almost certainly find you require more overhead, because of the two nested : loops. Yes, you could add a special test in the outer loop for already : being in the right place, but then you complicate the inner loop if you : want to avoid repeating this comparison. A bubble sort is certainly a : much simpler solution to the problem of optimal sorting of a sorted : list, and simplicity of solutoins is interesting if performance is NOT : an issue after all. Having just done some testing, I don't think I can agree with your statement about bubble sort being optimial on nearly sorted arrays. On the cases I tested insertion sort seems to be much quicker, unless the two arrays are so nearly sorted that I can't easily measure the time to sort them. I have not used any special cases of the sort you suggest in the insertion sort. The bubble sort function is also over 50% more code than the insertion sort so I can't call it simpler. Case 1: Take an array of 2000000 ints already sorted (the largest I could malloc). Reverse the order of elements [0]..[9], reverse the order [10]..[19],... Insertion sort 1 seconds, bubble sort 2 seconds Case 2: Take an array of 100000 ints already sorted. Swap the entry 1/3 of the way through with the one 2/3 of they way through. Insertion sort <1 seconds, bubble sort about 400 seconds HPUX A.09.05 using HP's ANSI C compiler with -O optimization. If you want to try it, here is the code (setup for case 2, change the two '#if 0's to '#if 1' to get case 1): #include #include #include void isort( int *a, size_t l ) { size_t i; for( i = 1; i < l ; i ++ ){ /* Insert a[i] into a[0]..a[i-1] */ int t = a[i]; size_t j = i; while( j > 0 && a[j-1] > t ){ a[j] = a[j-1]; j--; } a[j] = t; } } void bsort( int *a, size_t l ) { size_t i; int change = 1; for( i = l; change && (i > 0) ; i-- ){ size_t j; change = 0; /* Clear change flag */ /* one pass of bubbles */ for( j = 1; j < i ; j ++ ){ if( a[j-1] > a[j] ){ /*Swap */ int t; t = a[j]; a[j] = a[j-1]; a[j-1] = t; change = 1; } } } } void check( int const *a, size_t l ) { size_t i; for( i = 0; i < l ; i ++ ){ if( a[i] != i ) printf( "Error at entry %lu\n", (unsigned long)i ); } } void init( int *a, size_t l ) { size_t i; #if 0 size_t i1, i2; int t; for( i = 0; i < l ; i ++ ){ a[i] = i; } /* Swap elements at 1/3rds */ i1 = l/3; i2 = (2*l)/3; t = a[i1]; a[i1] = a[i2]; a[i2] = t; #else /* Assumes l is multiple of 10 */ for( i = 0; i < l ; i += 10 ){ size_t j; for( j = 0; j < 10; j++ ){ a[i+j] = i+9-j; } } #endif } #if 0 #define SZ (100000) #else #define SZ (2000000) #endif int main( void ) { /* Note assume unix - so time_t is integral seconds */ int *a = malloc( sizeof( int ) * SZ ); time_t t; init( a, SZ ); t = time(NULL); isort( a, SZ ); printf( "Time for Insertion sort of %ld ints is %ld\n", (long) SZ, (long)time(NULL) - (long)t ); check( a, SZ ); init( a, SZ ); t = time(NULL); bsort( a, SZ ); printf( "Time for Bubble sort of %ld ints is %ld\n", (long) SZ, (long)time(NULL) - (long)t ); check( a, SZ ); return 0; } -- 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?