Order by pair comparisons: Difference between revisions
Content added Content deleted
(→{{header|Lua}}: added Lua solution) |
(J) |
||
Line 909: | Line 909: | ||
Median number of comparisons: 13 |
Median number of comparisons: 13 |
||
Mean number of comparisons: 13.485714285714286</pre> |
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}}== |
=={{header|Java}}== |