I am making a comp. mathematical work, where I try to sort a sequence with a complex mathematical sorting algorithm that is not always defined between two elements in a sequence. I am trying to learn more about sorting algorithms that gracefully handle elementary comparisons that cannot be made, since so far I have only managed a very rudimentary approach.
My apologies if this question is some kind of classic problem and it takes me some time to determine it, the algorithmic design is not my strong suit.
Problem definition
Suppose I have a sequence A = {a, b, c, d, e} . Let define f(x,y) be a binary function that returns 0 if x < y and 1 if y <= x , using some complex sorting criteria.
Under normal conditions, this will provide us with enough granularity to sort A However, f can also return -1 if sorting criteria are not defined for this pair of pairs. The undefined pair of inputs is commutative, i.e., f(q,r) is undefined if and only if f(r,q) is undefined.
I want to try to sort the sequence A , if possible, with a specific sorting criterion.
For example, suppose that
f(a,d) = f(d,a) - undefined.- All other input pairs
f defined correctly.
Then, not knowing the inequality relationship between A and d , we can sort A based on clearly defined sorting criteria , while A and d not adjacent to each other in the resulting "sorted" sequence.
For example, suppose we first defined the relative sort A - {d} as {c, a, b, e} , since all these pairs in f defined correctly. In fact, this can cause any sorting algorithm.
Then we could call f(d,c) , and
- if
d < c we are done - the sorted sequence is really {d, c, a, b, e} . - Next, we move on to the next element in the sequence and try to call
f(a, d) . It is undefined, so we cannot set the position of d from this angle. - Then we call
f(d, e) and move from right to left through the element.- If we find some element
x , where d > x , we are done. - If we return to the comparison
f(a, d) again, we have found that we cannot sort our sequence based on the clear sorting criteria that we have.
Question
Is there a classification for these types of sorting algorithms that handle undefined comparison pairs?
Better yet , although not expected, is there a known “efficient” approach? I have defined my own extremely rudimentary brute force algorithm that solves this problem, but I am sure that it is not perfect.
It effectively simply throws out all the elements of the sequence that cannot be compared when detected, and sorts the remaining subsequence if any elements remain before completely trying to put all the elements of the sequence that are not comparable with all other elements in the sorted subsequence.
Just the way on which to continue the study of this topic would be wonderful - I lacked experience in using algorithms and, therefore, struggled to figure out where I should look for a few more prerequisites for these problems.