Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.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: Wed, 06 Jun 2012 08:10:36 -0500 Message-ID: <4FCF56CD.962@mindspring.com> Date: Wed, 06 Jun 2012 09:10:37 -0400 From: pete 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: <4FCD273B.5095@mindspring.com> <4fcdb0ef$0$6481$426a74cc@news.free.fr> <4FCEDA85.66BA@mindspring.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 104 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.223.87 X-Trace: sv3-wlH3WHUdz9xaPyCXeEoHDe37U7yTABoGW2mIKujRVRNWg0D2AzZEwwsBLKJlSlrvecAipH3n0bzqMMO!rzA9j8ccP99SRD6nSJXMYVTVlomU1rX9/8VPqNjL9OjahoU2AaXCW36zGrNmAqx2hGZUa1PMznd6!E/wYbEbO 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: 4860 Xref: csiph.com comp.lang.c:21904 Robert Wessel wrote: > > On Wed, 06 Jun 2012 00:20:21 -0400, pete > 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