You can get a three-result comparison from a boolean c by using it
twice, (c-c~). See https://www.jsoftware.com/papers/50/50_00.htm . If
this fails to distinguish elements then they are equivalent under the
ordering, so a stable algorithm has to maintain their input order.
It's my opinion that sorting function design is a lot cleaner with a
boolean comparison function. Modern quicksort hybrids such as pdqsort,
fluxsort, glidesort, and ipnsort (fluxsort and glidesort are stable)
always use one bit at a time. If they take a three-result comparison
then its result is always immediately compared to 0. So for example
(cmp(a, b) >= 0) could be written lt(b, a) with a less-than function.
Marshall
On Thu, Dec 21, 2023 at 04:52:58PM -0500, Raul Miller wrote:
> It's probably worth noting here that (for example) the quicksort
> algorithm relies on being able to tell whether items are equal. And a
> 0 1 result can't distinguish between ordering and equality. Many
> sorting implementations rely on a _1, 0, 1 result, as a consequence.
>
> That said, you could implement a sorting algorithm like bubble sort
> using a 0/1 result, and that could be a verb. (Also... rosettacode.org
> is currently down, due to a name server issue, but when it is up it
> has a decent collection of sorting algorithms implemented in J, and I
> think some of them could also be pressed into service here).
>
> Meanwhile, for aoc2023 day 7, the part 1 hand ranker could have been
> {{ (\:~ #/.~ y),'23456789TJQKA' i. y }}"1 (part 2 was slightly more
> complicated and of course migrated the 'J' to the first element of
> that character list.
>
> I hope this helps,
>
> --
> Raul
>
> On Thu, Dec 21, 2023 at 9:03 AM 'Viktor Grigorov' via Programming
> <programm...@jsoftware.com> wrote:
> >
> > Hey,
> >
> > Is there an easy way to sort an array with verb returning either 0 or 1,
> > like the comparison primitives?
> >
> > The verb that I'd in mind relates to the 2023's advent of code's day 7:
> > given two equal length hands, which one has the first high card. Which one
> > can write as:
> >
> > 'K2345' ( 2 | 0 { [: I. [: , [: (<,.>)/ ,: & ('23456789TJQKA'i.]) )
> > 'KJ2KA'
> > 0 NB. here meaning left is not greater right
> >
> > Cheers,
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
