javascript - Is there a black box method to detect if a sorting algorithm is stable? -


in javascript (somewhat applicable elsewhere), don't know target implementation code running on, there way feature detect if underlying sorting algorithm (of array.sort) stable or not, knowing follows the specification?

i find 2 tests in webkit (1) (2), how reliable tests? (could check done pcp?) i'm looking solution mathematically sound.

this tricky problem, since more advanced sorting algorithm can change subalgorithms depending on length of source array (like timsort). i've been confused since every test i've run has shown google chrome's sort stable, documentation i've seen has said it's unstable (the source tell why).

(typically, use this strategy make sorts stable; has small noticable performance impact)

source code sorting in various implementations:

black-box testing can not used determine program satisfies criterion unless can test possible inputs relevant criterion. black box free have lookup table maps inputs outputs (see pentium fdiv bug real-world lookup table bug) cannot sure tests preclude possibility of other input triggering violation.


Comments

Post a Comment

Popular posts from this blog

linux - xterm copying to CLIPBOARD using copy-selection causes automatic updating of CLIPBOARD upon mouse selection -

i've tried various ways coerce xterm (versions 285 , 292) copy selection clipboard clipboard whenever press ctrl-shift-c. promising way far has been, in ~/.xresources, put this: xterm*vt100.translations: #override \ ctrl shift <keypress> c: copy-selection(clipboard) \n\ ctrl shift <keypress> v: insert-selection(clipboard) ctrl-shift-v works perfectly, copying has nuance... if restart xterm, highlighting text puts things in primary clipboard; expected, proper, default behavior. if hit ctrl-shift-c, copies current selection clipboard clipboard. the bug, however, if highlight text after first time pressed ctrl-shift-c, you'll see highlighting copies both primary and clipboard. cannot figure out how stop xterm updating clipboard upon selection... , doesn't make sense me in first place. i said, @ specific point in time, copy selection clipboard... yet starts updating automatically upon selection after doing once... anyone have workaround...
Read more

c++ - qgraphicsview horizontal scrolling always has a vertical delta -

Image
i've subclassed qgraphicsview custom canvas used in cad application. i've reimplemented qgraphicsview::wheelevent check keyboard modifiers control key and, if control key pressed, zoom. i'm trying implement horizontal scroll when user holds shift , uses wheel. the problem i'm having horizontal scrolling always scrolls 0.279. not huge problem, hugely annoying , points else being wrong. so, here questions: is right way implement horizontal scrolling? if not, is? how eliminate delta of 0.279? thanks in advance. code , sample output below void myview::zoom(int delta) { double factor = pow(1.2, delta/abs(delta)); this->scale(factor, factor); } void myview::scrollhorizontal(int level) { qpointf center = maptoscene(viewport()->rect().center()); qdebug() << "center: " << center.x() << ", " << center.y(); centeron(qpointf(center.x() - level, center.y())); } void myview::wheelevent(qwheeleve...
Read more