Introducción
La clasificación de una matriz es uno de los primeros problemas graves estudiados en el curso clásico "Algoritmos y estructuras de datos" de la disciplina informática. En este sentido, las tareas de escribir clases y las preguntas correspondientes se encuentran a menudo en entrevistas como desarrollador interno o junior.
Formulación del problema
Tradicionalmente, vale la pena comenzar la presentación de soluciones al problema con su declaración. Por lo general, la tarea de clasificación implica ordenar una serie de enteros en orden ascendente. Pero, de hecho, esto es algo simplificación excesiva. Los algoritmos descritos en esta sección se pueden usar para ordenar una matriz de cualquier objeto entre el cual se establece una relación de orden (es decir, para cualquiera de los dos elementos podemos decir: el primero es mayor que el segundo, el segundo es mayor que el primero o son iguales). Puede ordenarlos tanto en orden ascendente como descendente. Utilizaremos la simplificación estándar.
Ordenar por insertos
La última vez hablamos sobre uno de los tipos más simples: el tipo de selección . Hoy nos centraremos en un algoritmo un poco más complejo: el tipo de inserción.
Descripción del algoritmo
La ordenación de una matriz por insertos se realiza de la siguiente manera: al igual que en el caso de la ordenación por selección, la matriz se divide en dos partes. Una parte se llama ordenada y la otra sin clasificar. El algoritmo supone atravesar toda la matriz para que la longitud de la parte ordenada sea igual a la longitud de toda la matriz. Dentro de cada iteración, tomamos el primer elemento de la parte no ordenada de la matriz y llevamos a cabo la siguiente operación: aunque nuestro elemento es estrictamente menor que el anterior, los intercambiamos. Luego aumentamos la longitud de la parte ordenada de la matriz en uno. Por lo tanto, al mover sucesivamente el elemento en estudio, logramos que encaje en su lugar. A continuación se presenta un ejemplo de una iteración:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6
Implementación
Sugiero mirar la implementación de este algoritmo en C:
void insertionSortFunction(double array[], int size) {
int i, j, temp;
// i , 1,
for (i = 1; i < size; i++) {
temp = array[i];
for (j = i - 1; j >= 0; j--) {
if (array[j] < temp) {
break;
}
array[j + 1] = array[j];
array[j] = temp;
}
}
}
Análisis
Propongo analizar este algoritmo.
La forma más fácil de comenzar el análisis es obtener las asintóticas de la memoria. Independientemente de la longitud y estructura de la matriz propuesta para la clasificación, la memoria se asigna solo para dos contadores de bucle y una variable auxiliar utilizada para intercambiar dos valores de variable. Por lo tanto, siempre es cierto:
...
Con el tiempo, todo es algo más interesante. El cuerpo del bucle interno toma O (1), es decir, no depende del tamaño de la matriz que se está ordenando. Esto significa que para comprender las asintóticas del algoritmo, es necesario contar cuántas veces se ejecuta este cuerpo. Pero el número de iteraciones del bucle interno depende de qué tan bien ordenados (o desordenados) estén los elementos de la matriz que se está ordenando. Varios casos deben ser analizados para su análisis.
Se alcanza el número mínimo de iteraciones si la matriz que se va a ordenar ya está ordenada. De hecho, para cada iteración del bucle for externo, se produce exactamente una iteración del bucle interno. Este es el llamado mejor caso .
Por lo tanto, la clasificación se realiza en tiempo lineal.
En el peor de los casos, se supone que el número de iteraciones es el más grande, es decir, la rotura nunca se dispara. En la primera iteración del bucle externo, se realiza una iteración del bucle interno. En la segunda iteración del bucle externo, se realizan 2 iteraciones del bucle interno. Continuando con el razonamiento, podemos llegar a la conclusión de que en la última (n - 1) - th) iteración del bucle externo (n - 1) se ejecutará la iteración del bucle interno. Obtenemos:
Para llevar a cabo los cálculos, utilizamos las propiedades de la notación O y la fórmula para la suma de una progresión aritmética.
En el caso promedio, se supone que el número de iteraciones del bucle interno para una iteración particular del bucle externo es igual a su valor promedio, es decir, la expectativa matemática. Suponga que todos los números permitidos del disparo del bucle interno son igualmente probables. En este caso, el número promedio de iteraciones del bucle interno es
. Se supone que soy el número de iteración del bucle externo. Ahora, para calcular las asíntotas, necesita calcular 
. Es decir, solo contamos cuántas veces se ejecuta el cuerpo del bucle interno. Por lo tanto, obtenemos 
.
Para resumir, la memoria asintótica del algoritmo es
a tiempo en el mejor de los casos
y en promedio y los peores casos
Por lo tanto, esta clasificación pertenece a la clase de clases cuadráticas .
También es importante tener en cuenta que la clasificación por selección es sólida en esta implementación . Permítame recordarle que la ordenación se llama estable si el orden de los elementos iguales no cambia durante su ejecución. Esta propiedad no es muy importante para una tarea educativa como clasificar una serie de números, pero si clasificamos algunos objetos más complejos con una relación de orden establecida, podría ser importante. Podemos considerar un ejemplo similar en algún momento la próxima vez que hablemos sobre la clasificación de radix.
Salir
Observamos otro tipo cuadrático: tipo de inserción, observamos su implementación robusta. La clasificación es principalmente educativa, aunque en la práctica se puede aplicar debido a buenos asintóticos en el mejor de los casos: si necesita agregar nuevos datos a una cantidad de datos suficientemente grande y ordenada para que todos los datos se vuelvan a ordenar, el bucle for interno puede ser útil. Por lo tanto, puede ser compatible con
orden del volumen de datos.
Aprende más sobre el curso.