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.
Tipo de selección
Uno de los tipos más simples es el de selección.
Descripción del algoritmo
La clasificación de una matriz por selección se realiza de la siguiente manera: 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, encontramos el mínimo en la parte no ordenada de la matriz e intercambiamos este mínimo con el primer elemento de la parte no ordenada de la matriz. Luego aumentamos la longitud de la parte ordenada de la matriz en uno. A continuación se presenta un ejemplo de una iteración:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8
Implementación
Sugiero mirar la implementación de este algoritmo en C:
void choiseSortFunction(double A[], size_t N)
{
for(size_t tmp_min_index = 0; tmp_min_index < N;
tmp_min_index++) {
//
for(size_t k = tmp_min_index + 1; k < N; k++) {
if (A[k] < A[tmp_min_index]) {
double min_value = A[k];
A[k] = A[tmp_min_index];
A[tmp_min_index] = min_value;
}
}
}
}
Análisis
Propongo analizar este algoritmo. 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. En la primera iteración del bucle externo, hay (n - 1) iteraciones del bucle interno. En la segunda iteración del bucle externo - (n - 2) iteraciones del bucle interno. Continuando con este razonamiento, llegamos a lo siguiente:
En el proceso de cálculos, primero usamos las propiedades de la notación O, y luego la fórmula para calcular la suma de una progresión aritmética.
Por orden, también es necesario estimar la memoria adicional que se requiere para ejecutar el algoritmo. Aquí todo es mucho más simple: asignamos memoria solo para los contadores de bucle y una variable, un búfer, que permite intercambiar 2 elementos de matriz. Por lo tanto:
Como resultado del análisis, llegamos a la conclusión de que la complejidad temporal del algoritmo depende del tamaño de la matriz de entrada de forma cuadrática. Por lo tanto, esta clasificación pertenece a la clase de clases cuadráticas . El resultado del análisis no depende del contenido de la matriz: es correcto en el mejor de los casos, peor y en promedio.
También es importante tener en cuenta que la clasificación por selección es sólida en esta implementación . Déjame recordarte que la clasificació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 ordenar 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.
Selección de selección a dos caras
La optimización del algoritmo implementado anteriormente puede ser de algún interés: mientras recorre la parte no ordenada de la matriz, puede buscar el máximo en paralelo con el elemento mínimo. Por lo tanto, después de la iteración, puede disminuir la parte no ordenada de la matriz no en uno, sino en dos. El algoritmo no mejora asintóticamente, pero sin embargo, la velocidad de su ejecución puede aumentar ligeramente, el número de comparaciones también se duplica.
Selección recursiva
Como ejercicio, puede intentar escribir un algoritmo no utilizando un bucle, sino utilizando la recursividad. En Java podría verse así:
public static int findMin(int[] array, int index){
int min = index - 1;
if(index < array.length - 1) min = findMin(array, index + 1);
if(array[index] < array[min]) min = index;
return min;
}
public static void selectionSort(int[] array){
selectionSort(array, 0);
}
public static void selectionSort(int[] array, int left){
if (left < array.length - 1) {
swap(array, left, findMin(array, left));
selectionSort(array, left+1);
}
}
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
Salir
Observamos uno de los tipos cuadráticos: selección de selección, observamos una implementación estable usando un bucle, recursión, discutimos la optimización del algoritmo mediante la reducción bidireccional de la parte no ordenada de la matriz. La clasificación es puramente educativa y no ha encontrado una amplia aplicación en la práctica.
Si desea obtener más información sobre el curso, invito a todos a un seminario web gratuito, que se realizará el 10 de julio .