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

Groups > comp.lang.c > #21904

Re: Breakthrough

Show key headers only | View raw

Robert Wessel wrote:
> 
> On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfiland@mindspring.com>
> wrote:
> 
> >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"}.
> 
> You're misreading the Wikipedia article. 

It says 
    "Unstable sorting algorithms can be specially
     implemented to be stable.""

> It actually says "One way of
> doing this is to artificially extend the key comparison, so that
> comparisons between two objects with otherwise equal keys are decided
> using the order of the entries in the original data order as a
> tie-breaker." 
> The critical bit is "the order of the entries in the
> *original* data order as a tie-breaker."  And that's quite correct. In
> the case of "distant" records with nominally equal keys, you're
> extending the comparison to be between (key, original record number)
> tuples.

But that is not one way of doing it,
that is only *part* of one way of doing it.

The example that I showed, 
*did* use the original order as a tie breaker.
To convert a nonstable algorithm to a stable one,
is more complicated
than just using the original order as a tiebreaker.

The article then says
"Remembering this order,  however, 
 often involves an additional computational cost."

But
 "Remembering this order" 
is more complicated than merely
 "additional computational cost."

"Remembering this order" also requires additional memory usage,
at which point it becomes simpler to stable sort using merge sort,
which merely requires the simple GT(A,B) macro.

A fast merge sort can be either done directly,
using a buffer half the size of the original array,
or if the element size is greater than (4 * sizeof(void *))
a fast merge sort can be done with less additional memory
using 2 arrays of pointers instead.


-- 
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