I have been working on the Dyalog APL quicksort implementation. The following programming puzzle arose in the process of doing the QA for this work.<\/p>\n
\u2375<\/code> is a simple array. Write a function sorted<\/code>, without using \u234b<\/code> or \u2352<\/code>, such that sorted \u2375<\/code> is 1 if \u2375<\/code> is sorted in ascending order and 0 otherwise.<\/div>\nThe point about not using grade<\/em> is that this is supposed to be an independent check that grade<\/i> is correct (remains correct) after the new work.<\/p>\nReal Vectors<\/h2>\n
The simplest case is when \u2375<\/code> is a numeric vector. If furthermore \u2375<\/code> are not complex numbers (a case addressed later), then<\/p>\n \u2227\/ 2\u2264\/\u2375\r\n<\/code><\/pre>\neach item being less than or equal to the next one, checks that \u2375<\/code> is sorted. Since \u234b<\/code> uses exact comparisons, here we must set \u2395ct\u2190\u2395dct\u21900<\/code>. Morever, in order that decimal floating-point numbers (DECFs) be compared correctly, here \u2395fr\u21901287<\/code>.<\/p>\nReal Arrays<\/h2>\n
More generally, when \u2375<\/code> is a non-complex numeric matrix, we must check that each row precedes or is equal to the next row. If c<\/code> and d<\/code> are consecutive rows, then corresponding items are compared and at the first item where they differ, c[i]<\/code> must be less than d[i]<\/code>.<\/p>\n ~ 0 \u220a (2>\u233f\u236a\u2375) \u2372 <\\ 2\u2260\u233f\u236a\u2375\r\n<\/code><\/pre>\nThe expression incorporates two refinements:<\/p>\n
\n- If
\u2375<\/code> is not a matrix, first apply \u236a\u2375<\/code>.<\/li>\n- Instead of checking
c[i]<\/code> is less than d[i]<\/code>, check that c[i]<\/code> is not greater than d[i]<\/code>. This finesses the case where c\u2261d<\/code> and there is no first item where they differ; that is, the case where <\\2\u2260\u233f\u236a\u2375<\/code> is all 0s for that row.<\/li>\n<\/ul>\n<\\<\/code>on a boolean vector has 0s after the first 1, (and is all 0 if there are no 1s). Therefore, <\\2\u2260\u233f\u236a\u2375<\/code> finds the first item (if any) where one cell differs from the next cell, and that item must not be greater than the corresponding item in the next cell.<\/p>\nFor example:<\/p>\n
x\u2190?97 3\u237410\r\n\r\n {~ 0 \u220a (2>\u233f\u236a\u2375) \u2372 <\\ 2\u2260\u233f\u236a\u2375} x\r\n0\r\n {~ 0 \u220a (2>\u233f\u236a\u2375) \u2372 <\\ 2\u2260\u233f\u236a\u2375} x[\u234bx;]\r\n1\r\n<\/code><\/pre>\n(Muse: since x<\/code> above are random numbers, there is a possibility that it is sorted and the first test above can be 1. But: if each elementary particle in the visible universe were a computer and every nanosecond each of them creates a random matrix and tests it for sortedness as above, running from the beginning of the time to the end of our lives, it is still a very<\/i> safe bet that no 1 would result.)<\/p>\nFor integer arrays, there is an alternative of using the signs of the arithmetic difference between successive cells:<\/p>\n
{~ 0 \u220a 1\u2260t\u00d7<\\0\u2260t\u2190 \u00d7 2-\u233f\u236a\u2375} x[\u234bx;]\r\n1\r\n<\/code><\/pre>\n(The sign where consecutive cells first differ must not be 1.) However, computing the difference on floating point numbers can founder on overflow:<\/p>\n
\u22a2 x\u2190\u00af1 1\u00d7\u230a\/\u236c\r\n\u00af1.79769E308 1.79769E308\r\n\r\n {~ 0 \u220a 1\u2260t\u00d7<\\0\u2260t\u2190 \u00d7 2-\u233f\u236a\u2375} x\r\nDOMAIN ERROR\r\n {~0\u220a1\u2260t\u00d7<\\0\u2260t\u2190\u00d72-\u233f\u236a\u2375}x\r\n \u2227\r\n<\/code><\/pre>\nComplex Numbers<\/h2>\n
Two complex numbers are ordered first by the real parts and then by the imaginary parts. (This is part of the TAO extension implemented in Dyalog APL version 17.0.) Therefore, a complex array can be tested for sortedness by testing an equivalent real array with each number replaced by their real and imaginary parts, thus:<\/p>\n
(\u00af1\u233d\u23731+\u2374\u2374\u2375) \u2349 9 11\u2218.\u25cb\u2375\r\n \u21919 11\u2218\u25cb\u00a8\u2375\r\n 9 11\u25cb\u23641 0\u22a2\u2375\r\n<\/code><\/pre>\nAlthough the second expression is the shortest, it is less efficient in time, space, and number of getspace<\/code> calls. The last expression is favored for its brevity and performance.<\/p>\nThe number of getspace<\/code> is a worthwhile measure. Part of the QA process is a rather stringent procedure called the “Shuffle QA”. The entire Shuffle QA takes several weeks to run and its running time is directly related to the number of getspace<\/code>.<\/p>\nCharacter Arrays<\/h2>\n
None of the functions < \u2264 \u2265 > - \u00d7<\/code> are permitted on characters. This is solved by application of \u2395ucs<\/code>, converting characters to integers while preserving the ordering.<\/p>\nPutting It All Together<\/h2>\nsorted\u2190{\r\n \u2395ct\u2190\u2395dct\u21900\r\n \u2395fr\u21901287\r\n d\u219010|\u2395dr \u2375\r\n d\u220a0 2: \u2207 \u2395ucs \u2375\r\n d=9: \u2207 9 11\u25cb\u23641 0\u22a2\u2375\r\n ~ 0 \u220a (2>\u233f\u236a\u2375) \u2372 <\\ 2\u2260\u233f\u236a\u2375\r\n}\r\n<\/code><\/pre>\nOther Considerations<\/h2>\n
That \u2375\u2337\u2368\u2282\u234b\u2375<\/code> is sorted is a necessary but not sufficient condition that \u234b\u2375<\/code> is correct. For example, an “adversary” can supply the following results for \u234b\u2375<\/code> so that \u2375\u2337\u2368\u2282\u234b\u2375<\/code> is sorted:<\/p>\n?\u2262\u2375\r\n(\u2262\u2375)\u2374?\u2262\u2375\r\n\u00af1\u2193\u234b\u2375\r\n\u220a i {\u2282\u2375[?\u2368\u2262\u2375]}\u2338\u2368 \u2375\u2337\u2368\u2282i\u2190\u234b\u2375\r\n<\/code><\/pre>\nThe last expression randomly permutes the grade indices of equal cells, a result which violates the requirement that grade<\/em> indices of equal cells are in ascending order. That is, grade<\/em> must be stable.<\/p>\nIn Dyalog APL version 17.0, grade<\/em> has been extended to work on non-simple arrays, the much discussed TAO, total array ordering. Checking that a non-simple array is sorted without using grade<\/em> requires facilities discussed in the paper TAO Axioms<\/em> and is beyond the scope of this note.<\/p>\n","protected":false},"excerpt":{"rendered":"Motivation I have been working on the Dyalog APL quicksort implementation. The following programming puzzle arose in the process of doing the QA for this work. \u2375 is a simple array. Write a function sorted, without using \u234b or \u2352, … Continue reading