Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 05 Jun 2012 23:20:20 -0500
Message-ID: <4FCEDA85.66BA@mindspring.com>
Date: Wed, 06 Jun 2012 00:20:21 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: Breakthrough
References: <jqi6o4$gqf$1@speranza.aioe.org> <4FCD273B.5095@mindspring.com> <4fcdb0ef$0$6481$426a74cc@news.free.fr>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 53
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.119
X-Trace: sv3-T4sOH7COzRXMbUPpIMulYzqXOg6Fwt9HSuTGxzN+a9kErkzn4iRiwTrrCGmAJVU+F9ZhzDDGSo+XjIQ!+gQj/LfsaHZ8q4lez8OPzUp+KUZ5vAKp74wzF0KHoZBQ8Ir9vyhAY8hrWOUow5DFSnQQtWx/0GqD!BXRGo9TJ3Fc=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2900
Xref: csiph.com comp.lang.c:21886

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