Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: **********@b*****.uk Date: Sun, 23 Jan 2022 19:10:47 -0800 Organization: A noiseless patient Spider Lines: 45 Message-ID: <86h79tomko.fsf@linuxsc.com> References: <20220123074300.987@kylheku.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="d742d26243a9575adb46fc0e29496190"; logging-data="742"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX191IdfVpcoY+ITDWDnExQcJLsz7Ci+dxDg=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:SO6EDWFXUmvxbBYNpK5gTTHGbZs= sha1:34k+4o8XLzl8GK414LLmKyW1t2o= Xref: csiph.com comp.lang.c:164565 Richard Damon writes: > On 1/23/22 10:48 AM, Kaz Kylheku wrote: > >> On 2022-01-17, Arslan RK wrote: >> >>> The data in the array may already be in the proper order or >>> near-proper order, so why make nine passes if fewer will suffice? >>> Modify the sort to check at the end of each pass if any swaps have >>> been made. If none have been made, then the data must already be >>> in the proper order, so the program should terminate. If swaps >>> have been made, then at least one more pass is needed. >> >> Your teacher is an ignoramus, or else you are trolling. >> >> The above termination test is part of the definition of Bubble Sort. >> >> https://en.wikipedia.org/wiki/Bubble_sort > > To my knowledge, there is no official legal definition of Bubble > Sort. The Naive Sort that doesn't test if it is done still falls > within what I would consider the family of 'Bubble Sort'. Checking > for no swaps, decreasing the bounds each loop by one, or to the last > swap, are all fairly standard improvements over the naive bubble > sort. > > For a class, starting with the simplest version (with not test) > and then showing ways to optimize, becomes a very good learning > experience and gets the students to actually THINK about what is > happening rather than just copy the algorithm. > > Then moving on to other improvements, like cocktails sort reversing > its pass each time can lead to a natural discussion of algorithms > and actually designing an algorithm rather than being stuck with > ones someone gives you. I agree on all points. Any algorithm that does repeated swapping scans may reasonably be called a bubble sort, even the horribly naive algorithm that starts again from the bottom whenver an out of order pair is found (and so typically has O( n*n*n ) runtime). One nice property of bubble sort from an educational perspective is that, because it is so simple, there are lots of obvious refinements to try. Furthermore all the obvious refinements are still pretty bad performance-wise, which serves as a springboard into more elaborate but better performing algorithms.