Usually considered the most inefficient sort algorithm, it happens to be quite suited to some frequently found data distributions, and thus it still used sometimes in professional products, even though this is quite an unsafe practice.
Complexity is O(n*n) both in number of comparisons and number of exchanges. Works well only when the distribution is almost sorted, with no small items at the end of the array.
class BubbleSort extends AlgoTri {
BubbleSort (int t, VueTris v) { super("Bubble
Sort", t, v); }
public void sort () {
boolean moved;
int curndx=size;
do {
moved=false;
for (int i=1; i <
curndx; i++) {
if (compare(i, i-1)<0) {
exchange(i, i-1);
moved=true;
}
}
curndx--;
} while (moved);
}
};
Shaker sort is a simple optimization that does passes in both directions, allowing out of place items to move fast across the whole array. Same complexity as Bubble sort, only works much better when some smal items are at the end of the array.
class ShakerSort extends AlgoTri {
ShakerSort (int t, VueTris v) { super("Shaker
Sort", t, v); }
public void sort () {
boolean moved=false;
int curmax=size, curmin=1;
do {
moved=false;
for
(int i=curmin; i < curmax; i++)
if (compare(i, i-1)<0) {
exchange(i, i-1);
moved=true;
}
curmax--;
if
(!moved) break;
for
(int i=curmax-1; i >= curmin; i--)
if (compare(i, i-1)<0) {
exchange(i, i-1);
moved=true;
}
curmin++;
} while (moved);
}
};