Given is a list of unique objects and an instance of an evaluator. The evaluator can compare three elements and returns the "middle" of the three. It has to take exactly three, and cannot compare between identical objects.
How could this list be sorted, when you can only compare elements in groups of three and know which one is between the other two, the middle one?
Since efficiency isn't a main concern, what algorithm could solve this? I had in mind a brute-force left and right pointer way, but this did not out very well for me. Other than that I could think of a sort of insertion sort, and maybe a quicksort with a pivot element (though a reliable pivot and partitions are not easy to configure)
public interface Evaluator {
/*
Compare three items.
Will return 0, 1 or 2, if respectively x0, x1 or x2 is the middle element of the three provided.
Comparing equal elements is undefined.
*/
int middleOf(Dish x0, Dish x1, Dish x2);
}
As the evaluator is given as a black box, I'll assume that it is not possible to define a maximum value as dummy to be used with the comparator, which would otherwise be the pragmatic way out.
If all the values we can work with are the values in the input array list, then it is possible to sort them, but not in a determined direction: it could come out as ascending or descending, and we wouldn't know which of the two was generated. This is a limitation that follows from how the comparator is defined. If you apply it to the values at index 𝑖, 𝑗, and 𝑘 (with 𝑖 < 𝑗 < 𝑘), the result will be the value at index 𝑗 when the list is sorted in ascending order and when it is sorted in descending order! So this comparator cannot distinguish between ascending and descending.
If we accept this limitation, we could use insertion sort to sort the list.
We start with the first two values in the array list and leave them as they are: we cannot use the evaluator here. The order of the first two elements will determine the final order (ascending or descending).
Then we keep taking the next value and shift the already sorted values until the slot is found where this next value has to be inserted -- this is the standard procedure tpyical for insertion sort. In more detail:
We take the first and last element from the already sorted partition and pass them with the new element to the comparator. If that evaluator returns the last element (from the sorted partition), then the next value is already at its right spot relative to the sorted partition.
If this is not the case, then we keep shifting values and call the comparator with the to-inserted value, the last value from the sorted partition, and the value before the "gap" made by the shift. We repeat this until the comparator returns the new value: that's when the gap is the insertion spot for the to-be-inserted value. If this never happens, then it means the value needs to be inserted before the very first value in the sorted partition.
Here is an implementation where I used int as data type for the input values. It generates a shuffled array list with the values 0 to 20, and then calls this insertion sort function. Finally it prints the result. As predicted above, this will sometimes output 0,1,2,...,20, and sometimes 20,19,18,...,0.
import java.util.*;
import java.util.stream.*;
interface Evaluator {
int middleOf(int x0, int x1, int x2);
}
public class Main {
// Blackbox function:
static Evaluator evaluator = (x, y, z) -> {
return x < y ? (y < z ? y : (x < z ? z : x))
: (y > z ? y : (x > z ? z : x));
};
public static void insertionSort(ArrayList<Integer> list) {
int n = list.size();
for (int i = 2; i < n; i++) {
int first = list.get(0);
int last = list.get(i-1);
int value = list.get(i);
// Not at the right spot?
if (evaluator.middleOf(first, last, value) != last) {
int j;
for (j = i-1; j > 0; j--) {
list.set(j + 1, list.get(j)); // Make room
if (evaluator.middleOf(list.get(j - 1), value, last) == value) {
// Found spot
list.set(j, value);
break;
}
}
if (j == 0) { // Value must become the first
list.set(1, first); // Make room
list.set(0, value);
}
}
}
}
public static void main(String[] args) {
// Prepare input
ArrayList<Integer> list = new ArrayList<>(
IntStream.rangeClosed(0, 20).boxed().toList()
);
Collections.shuffle(list);
System.out.println("input: " + list); // The shuffled input
insertionSort(list);
System.out.println("output: " + list); // The sorted output
}
}
Here are some of the outputs generated by consecutive runs:
input: [6, 11, 4, 3, 1, 0, 18, 14, 7, 9, 2, 5, 12, 19, 17, 8, 20, 16, 10, 15, 13]
output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
input: [11, 5, 0, 15, 13, 4, 8, 14, 7, 3, 18, 2, 12, 16, 10, 9, 6, 1, 17, 20, 19]
output: [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
input: [9, 16, 5, 18, 0, 13, 8, 6, 2, 17, 4, 12, 11, 19, 14, 15, 20, 3, 7, 10, 1]
output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]