Yeah, I was talking about a stable quicksort, like we see at
https://code.jsoftware.com/wiki/Essays/Quicksort
I guess if you don't care about search stability you can eliminate the
equality test against the pivot value.
Thanks,
--
Raul
On Thu, Dec 21, 2023 at 5:07 PM Elijah Stone <elro...@elronnd.net> 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
