Aquí una implementación (clásica) en Javascript (puede ejecutarse en un navegador o sugiero en Node.js)
puede ver que hay 3 funciones: swap, indexOfMininum y selectionSort;
Veamos la complejidad:
cada iteración SelectionSort (..) llame a IndexOfMinimum (..) y Swap;
La función de intercambio se ejecuta en tiempo constante sin importar cuán grande sea la matriz, y se llama n veces desde el ciclo dentro de SelectionSort (..) por lo que su complejidad es O (n), de hecho, todo lo que está dentro del ciclo de SelectionSort ( ..) se ejecuta en tiempo constante cada iteración por lo que su complejidad es O (n);
Las cosas comienzan a ponerse interesantes en indexOfMinimum (…) esta función se llama n veces y cada vez que ejecuta un bucle de código de tiempo constante, cada vez que se ejecuta el bucle de indexOfMinimum disminuye su contador total para la próxima iteración … así:
la primera vez se ejecuta n-1 veces, luego n-2, luego n-3, etc.
aquí llegaron las matemáticas, esta es una serie que en forma cerrada (estoy traduciendo estos términos del italiano … no sé si en inglés están bien) salió así:
- ¿Cuál es el significado o las aplicaciones del algoritmo KNN?
- ¿Cuáles son las debilidades del descenso de gradiente?
- Para una computadora, ¿qué tan aleatorio es ser aleatorio?
- ¿Por qué es necesario un relleno de palabra no utilizado al comienzo del espacio de almacenamiento dinámico asignado?
- ¿Las personas en la industria realmente usan el algoritmo K-Nearest Neighbour en la práctica?
[matemáticas] n ^ 2/2 + n / 2 (dejo de escribir el cálculo, lo siento pero el editor gana … ese es el resultado) [/ matemáticas]
ignoramos el factor 1/2 y tomamos en cuenta solo el term de orden máximo n ^ 2,
entonces la complejidad de indexOfMinimum es O (n ^ 2).
Entonces tenemos O (n) para cada cosa dentro de SelectionSort (sin IndexOfMinimum) y Swap, y O (n ^ 2) para IndexOfMinimum, podemos decir que el algoritmo SelectionSort tiene una complejidad asintótica de O (n ^ 2).
Otra consideración:
complejidad del mejor caso y el peor de los casos, podemos ver que este algoritmo no tiene ni el mejor caso ni el peor de los casos, IndexOfMinimum siempre ciclará n ^ 2 / n / 2 veces.
¿Cómo se escala? Si aumentamos la entrada en un factor de 1000, el tiempo de ejecución aumentará en un factor de 1 millón.
Espero que esta respuesta sea lo suficientemente clara.
var swap = function (array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var indexOfMinimum = function(array, startIndex) {
var minValue = array[startIndex];
var minIndex = startIndex;
for(var i = minIndex + 1; i < array.length; i++) {
if(array[i] < minValue) {
minIndex = i;
minValue = array[i];
}
}
return minIndex;
};
var selectionSort = function(array) {
var currentIndex=1;
for( var i = 0; i<array.length ; i++){
currentIndex = indexOfMinimum(array,i,currentIndex);
swap(array,i,currentIndex);
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
console.log("Starting Array: "+array);
selectionSort(array);
console.log("Array after sorting: " + array);
var desiredValue = [7, 9, 11, 22, 42, 88, 99]
console.log("must be equal to: " + desiredValue);
