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
