This is a stable algorithm because it only ever changes the order of
elements if one's less than the pivot and the other isn't. The problem
it has is that if elements compare equal but don't match then it'll
never get down to an array where ~.y has length 1. You get a stack error
on (<&:*qs _1 2 3) for example. A fix is to include a case when +/s is 0
that switches s to (~.y u~"_1 _ p) and returns if the sum is still 0.
Marshall
On Thu, Dec 21, 2023 at 02:07:18PM -0800, Elijah Stone wrote:
> The quicksort I know does not care whether elements are out of order.
> Example:
>
> qs=. {{ NB.quicksort adverb; u compare, y array
> if. 1>:#~.y do. y return. end. NB.ignore ~.
> p=. y{~?#y
> s=. y u"_1 _ p
> (u qs s#y) , (u qs (-.s)#y) }}
> <qs 10?@$10
> 0 0 2 3 3 3 6 6 9 9
> (<qs -: /:~) 10?@$10
> 1
>
> It is unstable, but that is to be expected. And it can be made stable
> without comparing for equality by pairing every element with its index.
>
> On Thu, 21 Dec 2023, 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
