1
\$\begingroup\$

I have devised a novel sorting algorithm, named Oracle Sort, which I believe is far superior to all currently known sorting algorithms (under certain assumptions). It utilizes an oracle to achieve a constant time complexity with regard to both the length of the input sequence and the number of distinct elements in the input sequence.

However, it seems that current computing is not yet ready for such an advanced algorithm, and therefore certain compromises had to be made and the algorithm had to be altered. As a result of these alterations, the performance of the provided algorithm has been much degraded. Therefore, I ask for any advice regarding the improvement of the time complexity of the algorithm as it stands.

Given below is an example implementation of the algorithm in Python 3.

from itertools import count, product

def oraclesort(input_seq):
  """
  Find a sequence (via enumeration), with is equal the sorted input sequence.

  Under ideal circumstances the enumeration would be done in parallel for all
  sequences of length up to at least the length of the input, and enumerating
  each of these sequences would take constant time. However, currently we are
  not able to achieve such results, so we have to resort to a less efficient
  sequential enumeration.

  The equality of enumerated candidate sequence and the sorted input sequence
  is determined by an oracle (the oracle_equals_sorted() function), which can
  tell in (assumed) constant time, whether the given candidate is equal to the
  sorted input. This, combined with the constant time needed to generate the
  candidates, gives us a total time complexity of O(1); the best known time
  complexity of an arbitrary-input sorting algorithm.
  """
  for i in count():
    for candidate_seq in product(input_seq, repeat=i):
      if oracle_equals_sorted(candidate_seq, input_seq):
        return candidate_seq

def oracle_equals_sorted(candidate_seq, input_seq):
  """
  Oracle which checks whether candidate_seq equals the sorted input_seq.

  The oracle should work in constant time (or ideally, in no-time), but we are
  limited to deterministic Turing Machines, and therefore, we are limited
  to certain implementations of the oracle, and these implementations happen
  to have non-optimal (eg. nonzero) time complexity.

  Despite being suboptimal, this implementation of the oracle is very elegant
  in that it internally uses the oracle sort to determine whether the given
  candidate sequence is equal to the sorted input sequence, hence completing
  a beautiful cycle of mutual recursion.
  """
  candidate_lst = list(candidate_seq)
  input_lst = list(input_seq)

  if not candidate_lst and not input_lst:
    return True

  if not candidate_lst or not input_lst:
    return False

  _, min_idx = min((val, idx) for idx, val in enumerate(input_lst))
  input_lst_without_min = input_lst[:min_idx] + input_lst[min_idx+1:]

  return candidate_lst[0] == input_lst[min_idx] and \
         candidate_lst[1:] == list(oraclesort(input_lst_without_min))
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm going to tag this as python, please include either python-2.x or python-3.x to reflect what version you used. \$\endgroup\$ – Linny Feb 16 '20 at 1:02
  • \$\begingroup\$ You might get better benchmark results if you measure the time complexity using a four-cornered day. \$\endgroup\$ – Samwise Feb 16 '20 at 5:16
  • 1
    \$\begingroup\$ @S.S.Anne This is definitely not \$O(n^2)\$. According to my (possibly imprecise) calculations, this has hyperfactorial time complexity in the worst case. I didn't try to figure out the exact space complexity, but it's probably going to be \$O(n^2)\$. \$\endgroup\$ – kyrill Feb 16 '20 at 23:51
  • \$\begingroup\$ @kyrill Ah, so it's worse than O(n^2). I wonder where the OP got the O(1) from, then... \$\endgroup\$ – S.S. Anne Feb 16 '20 at 23:53
  • \$\begingroup\$ Well apparently the O(1) complexity is under some pretty unrealistic assumptions, such as being able to consume arbitrary-length input in constant time (which is trivially impossible). \$\endgroup\$ – kyrill Feb 16 '20 at 23:54
3
\$\begingroup\$
  • well done providing doc strings
  • sticking to the Style Guide for Python Code makes Python code easier to grasp, especially for someone who didn't write it
  • to make the naming more convincing, you should factor out sequential_deterministic_stand_in_for_seeing_the_required_result() and sequential_deterministic_stand_in_for_checking_the_result()
    As a bonus, this removed implementation detail from the docstrings of "the oracle functions".
  • the nested loops in oraclesort() seem to iterate all permutations of elements from input_seq - as indicated in the docstring.
    Using itertools.permutations() is easier to read and should test sequences of like length, only.
    (Strictly faster than the related bogobogosort for not repeatedly checking the same sequence.)
  • instead of determining the index of the minimum value and using slices to construct input_lst_without_min, you could use just determine the minimum value, compare it to the start of the candidate sequence and remove it from the sequence to sort recursively:
    input_lst_without_min = input_seq[:]
    input_lst_without_min.remove(min(input_seq))
\$\endgroup\$
3
  • \$\begingroup\$ While your algorithm may be original, I doubt it's novelty - I'm pretty sure I've seen it before, if not remembering implementations. \$\endgroup\$ – greybeard Feb 16 '20 at 7:03
  • 2
    \$\begingroup\$ Recommended literature: en.wikipedia.org/wiki/Poe%27s_law \$\endgroup\$ – kyrill Feb 16 '20 at 13:01
  • \$\begingroup\$ @kyrill There are useful mindsets, procedures and habits doing code reviews just as in other parts of (software) development. Look at the code in the question with an eye on the coding, or reject the code because the implementation, as prominently stated in the question, (inevitably, for the time being) misses the main design goal - whatever you choose, make good use of your (and your readers') time. \$\endgroup\$ – greybeard Feb 16 '20 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.