2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think there have been times where my computer sorted an array with 100 million elements. What is n! When n = 100,000,000? Or n = 1,000? $\endgroup$ – gnasher729 Sep 29 at 19:06
  • $\begingroup$ If your concern is that the algorithm wouldn't work for large n, your right. The purpose of the algorithm wouldn't be to sort a list of data per se, but rather to show which comparisons lead to the shortest sorting algorithm. The idea would be that you would run this program, get some data on which steps can be used to sort a list of data quickly, and derive a sorting algorithm based on the data. For example, if merge sort required the least compares, you would get back that A<>B C<>D etc. then B<>D F<>H etc. etc. is the shortest branch for all n you tried. $\endgroup$ – Caleb Briggs Sep 29 at 21:01
1
$\begingroup$

Your method doesn't scale, since the complexity grows super-exponentially. For small $n$, the best known algorithm is Ford–Johnson, but it is known not to be optimal for larger $n$; this is explained in the linked Wikipedia entry.

Optimal algorithms for small $n$ are not necessarily unique, which makes it harder to generalize them. Moreover, the Ford–Johnson algorithm, which is such a generalization, isn't optimal for all $n$. So this kind of approach doesn't seem to work.

You can read about the state of the art in this pursuit in the OEIS entry A036604.

$\endgroup$
  • $\begingroup$ Yes the method doesn't scale all that well, that is true, but I think the resulting algorithms would generalize if you got a few data points. At the very least, I think they would be interesting to see. The state of the art approach seems to give the lower bound, but not HOW to get to the lower bound, ie which comaprisons result in the lower bound. This algorithm, if it were implemented, would give the steps. $\endgroup$ – Caleb Briggs Sep 29 at 22:13
  • $\begingroup$ Quoting Wikipedia: Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for $n$ items whenever $n \leq 15$ or $20 \leq n \leq 22$, and it has the fewest comparisons known for $n \leq 46$. For 20 years, merge-insertion sort was the sorting algorithm with the fewest comparisons known for all input lengths. However, in 1979 Glenn Manacher published another sorting algorithm that used even fewer comparisons, for large enough inputs. $\endgroup$ – Yuval Filmus Sep 29 at 22:16
  • $\begingroup$ I suggest reading some of the articles linked in the OEIS entry. They have methods superior to yours for finding the best algorithms for small $n$. $\endgroup$ – Yuval Filmus Sep 29 at 22:17
  • $\begingroup$ The algorithms that you shared are indeed much quicker for finding the minumum number of comparisons needed. But I couldn't seem to find what actual steps were taken to get to that result. What I'm really after is a list of steps that lead to that lower bound (e.g. compare element one with element two, then compare element three with element four). I think if there was enough solved examples, it might be possible to figure out the fastest sort method. $\endgroup$ – Caleb Briggs Sep 29 at 22:56
  • $\begingroup$ In response to the edits: Thats a great point that optimal algorithms aren't going to be unique for small values of n, so that would present a problem for generalizing. Still though, its much easier to check how an algorithm scales than it is to come up with the algorithm. Since the number of optimal algorithms probably decreases as n increases, pluggling in a larger value of n would give you a something that more generalizable. But still, an n large enough to be generalizable wouldn't be feasible to compute given this algorithm's time complexity. $\endgroup$ – Caleb Briggs Sep 29 at 23:24

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.