I was thinking about how many compares it takes to sort a list of comparable data, and I had an algorithm I was wondering the viability of.
(Its not unlikely that someone has come up with this before me [though I didn't find anything by researching it]. So if either this isn't useful, or someone has already come up with this, feel free to close the question.)
So heres my proposition for finding the fastest sorting algorithm. (With no elements equal to each other)
1: Create a list of n elements
2: Compare every permutation of elements (e.g. for [A,B,C] compare A to B, A to C, B to C).
3: The element can either be greater than or less than the element it is compared to, so each of these becomes a branch
4: Each of the elements then gains the information from that comparison (eg now A knows its greater than B in case 1, or now A knows its less than B in case 2)
5: Continue until all branches are finished.
I'm not too great at explaining, so let me include some examples.
I'll use the symbol "<>" to represent comparison @ = done ! = not done For n=3
[A,B,C]
*Start
A<>B A<>C B<>C
/ \ / \ / \
A>B A<B A>C A<C B>C B<C
B<>C A<>C B<>C A<>C B<>C A<>B A<>B B<>C A<>B A<>C A<>B A<>C
/\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\
@ ! ! @ ! @ @ ! ! @ ! @ @ ! ! @ @ ! ! @ ! @ @ !
I don't really have space to continue this, but all of the exclaimation points would end on the next iteration.
This shows how when comparing, 3 objects, its doesn't matter how you compare them, all methods are equally good, and end the same quickly.
My idea would be that by running this, you could find the best sort algorithm by adding the minumum from the left and the minimum of the right branch together. This would be recursive, so the shortest on the left branch of A<>B is The shortest of [B<>C A<>C].
So this algorithm would return which compares to do to get the list sorted. Since most sort algorithms, do about the same moves on any length list, if we get a couple of examples of the shortest algorithm, its probably feasible to figure out how to generalize it. At the very least, it allows us to compute the least amount of moves to sort a list (which is still an open problem https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list). You can safely ignore this section if you already know how you would implement this algorithm. The below code is just what I used to program what I have so far, and might be useful to clarify my ideas.
import java.util.ArrayList;
public class Compare {
/*
These are the objects to be compared, they include a list of integers that
corresponds to the locations of the objects greater than this object,
a list of integers represeting position for less than
And a list of integers that represent positions that corresponds thigns we don't know how relationship to
*/
public ArrayList<Integer> greater = null; //things this is GREATER than
public ArrayList<Integer> less = null; //things this is LESS than
public ArrayList<Integer> unknown = null;
int id;
Compare (int id) {
this.id = id;
unknown = new ArrayList<Integer>();
less = new ArrayList<Integer>();
greater = new ArrayList<Integer>();
}
public boolean is_defined(Integer other) {
return !in(unknown,other);
}
public void update_unknown(Compare[] items) {
//gets rid of all unknown that are already defined
all_greater(items);
all_less(items);
for (int i = 0; less.size() > i; i++) {
}
for (int i = 0; unknown.size() > i; i++) {
if (in(less,unknown.get(i)) || in(greater,unknown.get(i))) {
unknown.remove(i);
i--;
}
}
}
public boolean done() {
return (unknown.size() == 0);
}
public Compare copy() {
Compare res = new Compare(this.id);
res.greater = copy(greater);
res.less = copy(less);
res.unknown = copy(unknown);
return res;
}
public ArrayList<Integer> copy(ArrayList<Integer> c) {
ArrayList<Integer> res = new ArrayList<Integer>();
for (int i = 0; c.size() > i; i++) {
res.add(c.get(i));
}
return res;
}
public void compare(Compare other, boolean greater, Compare[] items) { //true if greater than other
if(greater) {
this.greater.add(other.id);
other.less.add(this.id);
}
else {
this.less.add(other.id);
other.greater.add(this.id);
}
this.update_unknown(items);
other.update_unknown(items);
}
public void all_greater(Compare[] items) {
for (int i = 0; greater.size() > i; i++) {
ArrayList<Integer> g =items[greater.get(i)].greater;
if(g != null) {
for (int j = 0; g.size() > j; j++) {
if (!in(greater,g.get(j))) {
greater.add(g.get(j));
}
}
}
}
}
public void all_less(Compare[] items) {
for (int i = 0; less.size() > i; i++) {
ArrayList<Integer> g =items[less.get(i)].less;
if(g != null) {
for (int j = 0; g.size() > j; j++) {
if (!in(less,g.get(j))) {
less.add(g.get(j));
}
}
}
}
}
public boolean in(ArrayList<Integer> list, Integer o) {
for (int i = 0; list.size() > i; i++) {
if (list.get(i) == o) {
return true;
}
}
return false;
}
public void init(Compare[] all) {
for (int i = 0; all.length > i; i++) {
if (all[i].id != this.id) {
unknown.add(all[i].id);
}
}
}
}
Sort Alg:
import java.util.ArrayList;
public class SortAlg {
Compare[] compares;
SortAlg(Compare[] compares) {
this.compares = compares;
}
public boolean done() {
for (int i = 0; compares.length > i; i++) {
if (compares[i].unknown.size() != 0) {
return false;
}
}
return true;
}
public String print() {
int res = 0;
for (int i = 0; compares.length > i; i++) {
res += compares[i].unknown.size();
}
return "" + res;
}
public static Compare[] init_r(int l) {
Compare[] c = new Compare[l];
for (int i = 0; l > i; i++) {
c[i] = new Compare(i);
}
for (int i = 0; c.length > i; i++) {
c[i].init(c);
}
return c;
}
public SortAlg copy() {
Compare[] res = new Compare[compares.length];
for (int i = 0; compares.length > i; i++) {
res[i] = compares[i].copy();
}
return new SortAlg(res);
}
}
Sorts:
import java.util.ArrayList;
public class Sorts {
ArrayList<SortAlg[]> sorts = new ArrayList<SortAlg[]>();
public void init(int sz) {
SortAlg a = new SortAlg(SortAlg.init_r(sz));
SortAlg[] items = new SortAlg[]{a};
sorts.add(items);
}
public ArrayList<Sorts> step() {
ArrayList<Sorts> res = new ArrayList<Sorts>();
for (int i = 0; sorts.size() > i; i++) {
for (int j = 0; sorts.get(i).length > j;j++) {
Sorts s = new Sorts();
s.sorts = perm(sorts.get(i)[j]);
res.add(s);
}
}
return res;
}
public ArrayList<SortAlg[]> perm(SortAlg s_) {
ArrayList<SortAlg[]> res = new ArrayList<SortAlg[]>();
for (int i = 0; s_.compares.length > i; i++) {
for (int j = i+1;s_.compares.length > j; j++ ) {
if ( !(s_.compares[i].done() && s_.compares[j].done()) && !(s_.compares[i].is_defined(j)) ) {
SortAlg[] tree = new SortAlg[2];
SortAlg s = s_.copy();
s.compares[i].compare(s.compares[j],true,s.compares); //going to have problems with memory addresses with this
tree[0] = s;
s = s_.copy();
s.compares[i].compare(s.compares[j],false,s.compares); //going to have problems with memory addresses with this
tree[1] = s;
res.add(tree);
}
}
}
return res;
}
}
One of the major problems of this algorithm is the speed. I believe that computing takes somewhere around the O(sum of n! from 1 to length of list).
But there are a lot of ways to speed it up. For example, you could make a greedy algorithm, which only moves down the paths which look promising, and then stop when you've gone above (log_2(n!)+1) deep (since that means your not looking at the shortest algorithm).
Also, the first step doesn't matter, so you can cut the algorithm down by however many permutation there are on the first step.
