0
$\begingroup$

Is it possible to reverse engineer sorting algorithm (sorting by comparisons) by sequences of indices of compared elements? We can input any lists of numbers arbitrarily many times. Comparison to existing algorithms and their corresponding sequences is not allowed. Further tests can alter algorithm, so task can be restricted: use only limited number of test sequences and find one of simplest algorithms which match corresponding indices.

EDIT: Example: This is full tree of comparisons for n = 4. Tuple (0, 1, -1, 0) means that second element is larger then third. I forgot to mention that all comparisons are strict. Start of tree reads so: First element is larger than second, third larger than fourth, second larger than fourth, second larger than third. That's all, we have sorted sequence. By not allowing comparison to existing algorithms I assume that we have some new algorithm (this tree does not represent it), which have different sequence of comparisons. Actually my problem not about sorting at all, I just chose appropriate analogy.

(1, -1, 0, 0)
  (0, 0, 1, -1)
    (0, 1, 0, -1)
      (0, 1, -1, 0)
      (0, -1, 1, 0)
        (1, 0, -1, 0)
        (-1, 0, 1, 0)
    (0, -1, 0, 1)
      (1, 0, 0, -1)
        (1, 0, -1, 0)
        (-1, 0, 1, 0)
      (-1, 0, 0, 1)
  (0, 0, -1, 1)
    (0, 1, -1, 0)
      (0, 1, 0, -1)
      (0, -1, 0, 1)
        (1, 0, 0, -1)
        (-1, 0, 0, 1)
    (0, -1, 1, 0)
      (1, 0, -1, 0)
        (1, 0, 0, -1)
        (-1, 0, 0, 1)
      (-1, 0, 1, 0)
(-1, 1, 0, 0)
  (0, 0, 1, -1)
    (1, 0, 0, -1)
      (1, 0, -1, 0)
      (-1, 0, 1, 0)
        (0, 1, -1, 0)
        (0, -1, 1, 0)
    (-1, 0, 0, 1)
      (0, 1, 0, -1)
        (0, 1, -1, 0)
        (0, -1, 1, 0)
      (0, -1, 0, 1)
  (0, 0, -1, 1)
    (1, 0, -1, 0)
      (1, 0, 0, -1)
      (-1, 0, 0, 1)
        (0, 1, 0, -1)
        (0, -1, 0, 1)
    (-1, 0, 1, 0)
      (0, 1, -1, 0)
        (0, 1, 0, -1)
        (0, -1, 0, 1)
      (0, -1, 1, 0)
$\endgroup$
4
  • $\begingroup$ What would count as "reverse engineer" for you? Surely it is possible; you can running the algorithm on all $n!$ permutations of $n$ elements. What do you mean by "not allowed"? How can something "not be allowed"? I get to define what my algorithm does; it can do any computation I want, and it's none of your business (how would you know? for all you know maybe my algorithm is a crazily-obfuscated way of doing the thing you don't want to allow -- how could you tell?). Finally, I don't understand your last sentence. Can you edit the question to make it more clearly defined? $\endgroup$
    – D.W.
    Commented Apr 19, 2017 at 21:17
  • 1
    $\begingroup$ What do you observe when you run the algorithm? If you already know it's a sorting algorithm, what are you trying to find out? $\endgroup$ Commented Apr 20, 2017 at 6:20
  • $\begingroup$ I try to find programming code for this algorithm. $\endgroup$
    – DSblizzard
    Commented Apr 20, 2017 at 7:12
  • $\begingroup$ @D.W.: More data can alter our guess of algorithm. For example, "algorithm" can be just full set of special cases and as a result we cannot know how it will sort n+1 elements even if we looked at process of it work for 1 ... n elements. So we should somehow restrict set of possible algorithms. I offer such restriction that we should consider only simplest (shortest) algorithm which do the job. $\endgroup$
    – DSblizzard
    Commented Apr 20, 2017 at 7:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.