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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/14 Message-ID: #1/1 X-Deja-AN: 174147708 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-14T00:00:00+00:00 List-Id: 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. So Step