Order by pair comparisons: Difference between revisions
J
(→{{header|Lua}}: added Lua solution) |
(J) |
||
Line 909:
Median number of comparisons: 13
Mean number of comparisons: 13.485714285714286</pre>
=={{header|J}}==
Implementation (here we assume that ordering is transitive):<lang J>require'general/misc/prompt'
sel=: {{ u#[ }}
quicksort=: {{
if. 1 >: #y do. y
else.
(quicksort y less sel e),(y =sel e),quicksort y less~ sel e=.y{~?#y
end.
}}
ptc=: {{
t=. (+. +./ .*.~)^:_ y=1
j=. I.,t+.|:t
($y)$(j{,t) j} ,y
}}
less=: {{
coord=. x ,&(items&i.) y
lt=. LT {~<coord
if. 1<lt do.
lt=. 'y' e. tolower prompt 'Is ',(":;x),' less than ',(":;y),'? '
LT=: ptc (lt,-.lt) (coord;|.coord)} LT
end.
lt
}}"0
asksort=: {{
items=: ~.y
LT=: <:%=i.#items
quicksort y
}}</lang>
Task example:<lang J> asksort&.;:' violet red green indigo blue yellow orange'
Is indigo less than violet? yes
Is indigo less than red? no
Is indigo less than green? no
Is indigo less than blue? no
Is indigo less than yellow? no
Is indigo less than orange? no
Is yellow less than red? no
Is yellow less than green? yes
Is yellow less than blue? yes
Is yellow less than orange? no
Is green less than blue? yes
Is red less than orange? yes
red orange yellow green blue indigo violet</lang>
=={{header|Java}}==
| |||