Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Sort char array
Date: Wed, 09 Oct 2019 02:06:13 -0700
Organization: A noiseless patient Spider
Lines: 19
Message-ID: <86tv8i8f0a.fsf@linuxsc.com>
References: <STKlF.8551$oU2.5908@fx21.iad> <qnaaqc$uu0$1@news.albasani.net> <qnac0l$sjq$1@news.albasani.net> <UJ2mF.14810$oA2.14023@fx08.iad> <5d98ba3c$0$3549$426a34cc@news.free.fr> <060baff1-974b-41b0-bba7-7c28a2681dc9@googlegroups.com> <5d99bad9$0$14392$426a74cc@news.free.fr> <87k19hnc0o.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="c0077320ebba5bb8d2e49a5d4c287ef2"; logging-data="842"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18sx6QnScfW+LbDrBNnTM0HavPaj7FEwwI="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:Q+8BdPTzaqyragy0iRqTayp6v9s= sha1:/ALUB1jEAw0Tg3+U6s6A9ohjGhU=
Xref: csiph.com comp.lang.c:146790

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>> [...]
>
> For what it's worth, I say an algorithm needs both to qualify as a
> bubble sort:  comparison between adjacent elements, and to stop
> "bubbling" when the array is sorted.  If you ask CS people to say what
> they know about bubble sort, I'm confident you'd get at least these two
> facts:  that it's O(n^2) in general, and that it's O(N) for sorted data.

To me only the swap-wrongly-ordered-adjacent-elements property is
necessary to be called a bubble sort.  Early termination is a
useful optimization but not (in my personal lexicon) an essential
element of a "bubble sort" algorithm.

I should add though that I learned about different sorting methods
before Knuth volume 3 was published.  So it could be that what is
accepted terminology now differs from what I learned those oh so
many years ago.