Saturday, 17 August 2013

How to improve selection sort?

How to improve selection sort?

This is more of an academic/homework question?
Would it be better to change
if (index_outer !== index_min) {
$P.swap(arr, index_outer, index_min);
}
to
$P.swap(arr, index_outer, index_min);
and always swap, as this is the special case when index_outer does have
the smallest value? It would be a swap that does nothing, but at the same
time it would not break anything. Because this does not happen often I
suppose, it would reduce the amount of times an if check was used.
$P.swap = function (arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
$P.selectionSort = function (arr) {
var index_outer,
index_inner,
index_min,
length = arr.length;
for (index_outer = 0; index_outer < length; index_outer++) {
index_min = index_outer;
for (index_inner = index_outer + 1; index_inner < length;
index_inner++) {
if (arr[index_inner] < arr[index_min]) {
index_min = index_inner;
}
}
if (index_outer !== index_min) {
$P.swap(arr, index_outer, index_min);
}
}
return arr;
};

No comments:

Post a Comment