The regular insertion sort is the most efficient of the 3 main naive approaches.
class InsertSort extends AlgoTri {
InsertSort (int t, VueTris v) { super("Insertion Sort", t,
v); }
public void sort () {
for (int i = 1; i < size; i++) {
for (int j = i; j > 0; j--)
{
if (compare(j, j-1)<0)
exchange(j, j-1);
else break;
}
}
}
};
Dichotomic insertion (also called binary search insertion sort) consists in using a dichotomic search to determine where to insert the new item, taking advantage of the fact the sub array is already sorted. This yield the most efficient algorithm in terms on number of comparisons, with a guaranteed bound of sum(log2 i) for i in [1..n-1], or log2 (n-1)!, which is strictly less than n log2 n. Unfortunately, this algorithm is not efficient in practice, because, to the opposite of Selection sort, it does on average of n*n exchanges. There are two variants, depending if we assume the array to be almost sorted (DichoSort) or random or inverted (DichoSort2): in the first case, a first comparison is made with the top item in the already sorted array, which avoids entering the loop of dichotomic search each time the new item is at its proper place.
class InsertDichoSort extends AlgoTri {
InsertDichoSort (int t, VueTris v) { super("Insert-Dicho",
t, v); }
public void sort () {
for (int i = 1; i < size; i++) {
// find by dichotomy before which item to insert the current
if (compare(i-1,i) <= 0) continue;
int binf=0, bsup=i-1;
do {
int mid=(bsup+binf)/2;
int res=compare(mid,i);
if (res < 0) binf=mid+1;
else if (res > 0) bsup=mid;
else binf=bsup=mid+1;
} while (bsup > binf);
// now insert it before binf
int val=item(i);
for (int k = i; k > binf; k--)
exchange(k, k-1);
assign(binf,val);
}
}
};
class InsertDichoSort2 extends AlgoTri {
InsertDichoSort2 (int t, VueTris v) { super("Insert-Dicho2",
t, v); }
public void sort () {
for (int i = 1; i < size; i++) {
// find by dichotomy before which item to insert the current
int binf=0, bsup=i-1;
int mid=(bsup+binf)/2;
do {
int res=compare(mid,i);
if (res < 0) binf=mid+1;
else if (res > 0) bsup=mid;
else binf=bsup=mid+1;
mid=(bsup+binf)/2;
} while (bsup > binf);
// now insert it before binf
if (mid < i-1) {
int val=item(i);
for (int k = i; k > mid; k--)
exchange(k, k-1);
assign(mid,val);
} else if (compare(i-1,i) > 0)
exchange(i,i-1);
}
}
};