Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #21886

Re: Breakthrough

Show all headers | View raw

Noob wrote:
> 
> pete wrote:
> 
> > I've never needed the three way comparison
> > to implement any sorting algorithm.
> >
> > It has always been sufficient for me
> > to merely use a (Greater Than) macro, GT(A, B),
> > to implement any sorting algorithm.
> >
> > #define GT(A, B)     ((*A)->Data > (*B)->Data)
> >
> > I have never needed to know whether two keys compare equal,
> > in order to implement a sorting algorithm.
> 
> Perhaps it is needed when writing "stable" sorting algorithms?
> http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

No. Definitely not.
When implementing any of the inherently stable algorithms,
such as bubble sort, insertion sort or merge sort,
it is sufficient to know only 
whether or not the two keys being compared, are out of order. 

The wikipedia article claims that the order
of the keys can be used as a tie breaker to convert 
an unstable algorithm into a stable one, 
but that is wrong because,
when two distant unequal keys are compared,
the only way to maintain stability
between those two keys and all of the keys in between them,
is to move all of the keys in between them.

Example:
Suppose you have this array:

    char numbers[][sizeof "eight"] = {"seven","eight","six"};

and you want to do a stable sort according to string length,
the result of a stable sort would be {"six","seven","eight"}.

If you sorted {"seven","eight","six"}
by using a non stable sort such as simple selection sort,
using the key addresses as a tie breaker,
"seven" would not be out of order compared to "eight",
regardless of whether their addresses were used as a tie breaker.
But when "seven" was compared to "six",
those two keys would be out of order and swapped
with the final sort result being {"six","eight","seven"}.

-- 
pete

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
  Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
    Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
      Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
          Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
            Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
              Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
                Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
      Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
        Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
      Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
      Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
        Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
          Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
            Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
              Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
      Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
  Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
      Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
        Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
          Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
  Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
    Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
      Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
      Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
        Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
          Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
            Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
              Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
                Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
                Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
                Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
                Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
  Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
    Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200

csiph-web