O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity. Selecting the lowest element requires scanning all n elements (this takes 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, for (n – 1) + (n – 2) + … + 2 + 1 = n(n – 1) / 2 =O(n2) comparisons. Each of these scans requires one swap for n – 1 elements (the final element is already in place). Thus,the comparisons dominate the running time, which is O(n2).
public class SelectionSort {
public int[] sort(int[] data) {
int minIndex;
for (int i = 0; i < data.length; i++) {
minIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
return data;
}
public static void main(String[] args) {
int[] data = new int[] { 8,15,4,23,16,42 };
System.out.println(Arrays.toString(new SelectionSort().sort(data)));
}
}
Advertisement
