Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Isn't that beauty ? (no it's not)
Date: Sun, 12 Apr 2026 11:16:50 -0700
Organization: A noiseless patient Spider
Lines: 68
Message-ID: <86bjfo82nh.fsf@linuxsc.com>
References: <10otm7r$1ntrg$1@raubtier-asyl.eternal-september.org> <10ovlm7$2ijcp$1@raubtier-asyl.eternal-september.org> <10p1r1q$3hfeq$1@dont-email.me> <10p2q41$3umkh$1@raubtier-asyl.eternal-september.org> <10p2ssl$3ven8$1@dont-email.me> <10p30j2$13nd$1@raubtier-asyl.eternal-september.org> <10p30kr$13nd$2@raubtier-asyl.eternal-september.org> <10p3jgn$80c7$1@dont-email.me> <10p9q0h$2a77o$1@dont-email.me> <10pa02q$2d5us$1@dont-email.me> <10pa4eg$2dtli$5@dont-email.me> <10pa78l$2fjaa$1@dont-email.me> <10palrv$2jpeu$2@dont-email.me> <10pbf0q$2rtq3$1@dont-email.me> <10pbg8f$2spms$2@dont-email.me> <10pbhud$2tbk0$2@dont-email.me> <10pcvr2$3ednq$2@dont-email.me> <20260318112151.000021dc@yahoo.com> <10pdu8k$3o60c$1@dont-email.me> <20260319111959.0000447c@yahoo.com> <86fr57xhf2.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sun, 12 Apr 2026 18:16:53 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="425f3de481b107cac4c4e410f9a2c2b8"; logging-data="2887355"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+lR1CGiyATbZgl4Jnc+N6Q8VIORj5/G2Y="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:2lcNwp4Lz/9fL8EmPOp3pdt1+SU= sha1:FtOu9zQ29cyIjjrvQSqRxeXLii4=
Xref: csiph.com comp.lang.c:397510

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[...]

After my previous posting I got curious about how different sorting
algorithms behave for "nearly sorted" inputs.  I decided to run some
trials for some of the sorting functions given in my last posting.
Here are the results:

  Average number of compares for sorting 100 elements, with one
  element out of place:

             insertion sort     132.647
                 gnome sort     166.293
             ping pong sort     180.177
          knuth bubble sort     956.500

  Average number of compares for sorting 100 elements, with two
  elements out of place:

             insertion sort     166.126
                 gnome sort     233.253
             ping pong sort     234.163
          knuth bubble sort    1566.487

My conclusion, based on the above, is that bubble sort has nothing
to recommend it as a practical sorting algorithm, even considering
the refinement of early pruning (called the "knuth bubble sort" in
the list above).  The gnome sort is both simpler and better in terms
of performance.

Incidentally, some years ago I devised a variation of gnome sort,
which I call "leaping gnome sort".  A leaping gnome sort is like
gnome sort when going right to left, that is, when the elements
being looked at are out of order, swap them and move one place to
the left.  When no swap is needed, the gnome "leaps" to the last
place a rightward shift was initiated.  In terms of code, leaping
gnome sort can be written as follows:

   void
   leaping_gnome_sort( unsigned n, Element a[n] ){
      for(
         unsigned i = 1, j = 2;
         i < n;
         i =   follows(i-1,i,a)  ? swap(i-1,i,a), i>1 ?i-1 :j++   : j++
      ){}
   }

The "leaping" behavior is evident whenever the current location 'i'
gets the value 'j++' rather than 'i-1'.

Of course this algorithm could be written using a while() loop
rather than a for() loop:

   void
   leaping_gnome_sort( unsigned n, Element a[n] ){
      unsigned i = 1, j = 2;
      while(  i < n  ){
         if(  !follows(i-1,i,a)  )  i = j++;
         else {
            swap(i-1,i,a);
            i =  i > 1  ? i-1  : j++;
         }
      }
   }

In either case it's nice having only a single loop structure rather
than an outer loop and a second, nested loop.