Probably the most natural sort of all. My take is that 70% of newcomers faced to sorting an array will come up with this solution. This sort is the worst algorithms in numbers of comparisons: n(n+1)/2 compares in all cases. Yet is the most efficient of all the currently known algorithms in terms of exchanges: at most n-1 exchanges.
class SelectSort extends AlgoTri {
SelectSort (int t, VueTris v) { super("Selection Sort", t,
v); }
public void sort () {
for (int i = 0; i < size; i++) {
int curmin = i;
for (int j = i+1; j < size; j++) {
if (compare(j, curmin)<0)
curmin=j;
}
if (curmin != i)
exchange(curmin, i);
}
}
};
Exercise (advanced):
Design a more efficient algorithm in numbers of exchanges, without sorting the array in a buffer, then making only requested changes. Hint: use statistics on the data distribution.