Selection sort selects the minimum by scanning n elements, taking n-1 comparisons, and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n-1 elements and so on.
SelectionSort.java
0
1
2
3
4
5
6
7
8
9
function selectionSort(a) {
var N = a.length;
for (var i = 0; i < N; i++) {
var min = i;
for (var j = i+1; j < N; j++) {
if (a[j] < a[min]) min = j;
}
exch(a, i, min);
}
}
Selection sort is the simplest sorting algorithm to understand. However, in order to sort, it needs to do lots of comparisons: (n-1) + (n-2) + (n-3) ...+ 1 = n x (n-1)/2. When n is very large, the amount of computations are roughly proportional to n square. So in the terms of computation complexity, it is the most complex algorithm, with complexity of O(n^2).
Fun fact:
Embedded system such as FPGA can customize hardware for specific task. Fine tune the hardware by the character of less swap is needed, the FPGA can allocate faster computation units to comparison operation, but slower computation units to swap operation, in order to achieve the best cost/effect of the hardware resource.
 |
| FPGA |
 |
| hardware programing code |
Next>
