Share
En esta sección, veremos cinco algoritmos utilizados para ordenar los datos en una matriz. Comenzaremos con un algoritmo ingenuo, clasificación de burbujas, y terminaremos con el algoritmo de clasificación de propósito general más común, clasificación rápida.
Con cada algoritmo explicaré cómo se realiza la clasificación y también proporcionaré información sobre la complejidad mejor, promedio y en el peor de los casos, tanto para el rendimiento como para el uso de la memoria..
Para mantener el código del algoritmo de clasificación un poco más fácil de leer, una Intercambiar El método será utilizado por cualquier algoritmo de clasificación que necesite intercambiar valores en una matriz por índice.
void Swap (T [] items, int left, int right) if (left! = right) T temp = items [left]; elementos [izquierda] = artículos [derecha]; elementos [derecho] = temp;
| Comportamiento | Ordena la matriz de entrada usando el algoritmo de clasificación de burbujas. | ||
| Complejidad | Mejor caso | Caso medio | Peor de los casos |
| Hora | En) | En2) | En2) |
| Espacio | O (1) | O (1) | O (1) |
La clasificación de burbujas es un algoritmo de clasificación ingenuo que funciona al realizar múltiples pasadas a través de la matriz, cada vez que se mueve el valor sin clasificar más grande a la derecha (final) de la matriz.
Considere la siguiente matriz de enteros sin clasificar:
Matriz sin clasificar de enteros En el primer paso a través de la matriz, se comparan los valores tres y siete. Dado que siete es mayor que tres, no se realiza ningún intercambio. A continuación, se comparan siete y cuatro. Siete es mayor que cuatro, por lo que los valores se intercambian, por lo que se mueve el siete, un paso más cerca del final de la matriz. La matriz ahora se ve así:
Los 4 y 7 han intercambiado posiciones. Este proceso se repite, y los siete finalmente se comparan con los ocho, que es mayor, por lo que no se puede realizar ningún intercambio, y el paso finaliza al final de la matriz. Al final del paso uno, la matriz se ve así:
La matriz al final de la pasada 1 Debido a que se realizó al menos un intercambio, se realizará otro pase. Después de la segunda pasada, los seis se han movido a la posición..
La matriz al final de la pasada 2 Nuevamente, debido a que se realizó al menos un intercambio, se realiza otro pase.
El siguiente paso, sin embargo, encuentra que no se necesitaron swaps porque todos los artículos están ordenados. Dado que no se realizaron swaps, se sabe que la matriz está ordenada y el algoritmo de clasificación está completo.
Public void Sort (T [] items) bool swapped; do intercambiado = falso; para (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (elementos, i - 1, i); swapped = true; while (swapped! = false);
| Comportamiento | Ordena la matriz de entrada usando el algoritmo de ordenación por inserción. | ||
| Complejidad | Mejor caso | Caso medio | Peor de los casos |
| Hora | En) | En2) | En2) |
| Espacio | O (1) | O (1) | O (1) |
La ordenación por inserción funciona haciendo una sola pasada a través de la matriz e insertando el valor actual en la porción ya ordenada (comienzo) de la matriz. Después de procesar cada índice, se sabe que todo lo que se ha encontrado hasta ahora está ordenado y todo lo que sigue es desconocido..
Esperar lo?
El concepto importante es que la ordenación por inserción funciona ordenando los elementos a medida que se encuentran. Ya que procesa la matriz de izquierda a derecha, sabemos que todo a la izquierda del índice actual está ordenado. Este gráfico muestra cómo la matriz se ordena a medida que se encuentra cada índice:
Una matriz que se está procesando por orden de inserción A medida que el procesamiento continúa, la matriz se vuelve más y más ordenada hasta que está completamente ordenada.
Veamos un ejemplo concreto. La siguiente es una matriz sin clasificar que se ordenará mediante la ordenación por inserción.
Matriz sin clasificar de enteros Cuando comienza el proceso de clasificación, el algoritmo de clasificación comienza en el índice cero con el valor tres. Como no hay valores que preceden a esto, se sabe que la matriz hasta e incluyendo el índice cero está ordenada.
El algoritmo luego pasa al valor siete. Dado que siete es mayor que todo en el rango ordenado conocido (que actualmente solo incluye tres), se sabe que los valores hasta siete incluidos están en orden de clasificación.
En este punto, se sabe que los índices de matriz 0-1 están ordenados y 2-n se encuentran en un estado desconocido.
El valor en el índice dos (cuatro) se marca a continuación. Dado que cuatro es menos de siete, se sabe que cuatro deben moverse a su lugar adecuado en el área del arreglo ordenado. La pregunta ahora es en qué índice de la matriz ordenada debe insertarse el valor. El método para hacer esto es el FindInsertionIndex se muestra en el ejemplo de código. Este método compara el valor a insertar (cuatro) con los valores en el rango ordenado, comenzando en el índice cero, hasta que encuentra el punto en el que se debe insertar el valor.
Este método determina que el índice uno (entre tres y siete) es el punto de inserción apropiado. El algoritmo de inserción (el Insertar Método) luego realiza la inserción eliminando el valor que se insertará de la matriz y desplazando todos los valores del punto de inserción al elemento eliminado a la derecha. La matriz ahora se ve así:
Array después de la primera inserción de algoritmo Ahora se sabe que la matriz del índice cero a dos está ordenada, y se desconoce todo, desde el índice tres hasta el final. El proceso ahora comienza nuevamente en el índice tres, que tiene el valor cuatro. A medida que el algoritmo continúa, se producen las siguientes inserciones hasta que se ordena la matriz.
Array después de nuevos algoritmos de inserción Cuando no haya más inserciones por realizar, o cuando la parte ordenada de la matriz sea la matriz completa, el algoritmo se habrá completado..
Accentsconagua
Public void Sort (T [] items) int sortedRangeEndIndex = 1; while (ordenadoRangeEndIndex < items.Length) if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); Insert(items, insertIndex, sortedRangeEndIndex); sortedRangeEndIndex++; private int FindInsertionIndex(T[] items, T valueToInsert) for (int index = 0; index < items.Length; index++) if (items[index].CompareTo(valueToInsert) > 0) índice de retorno; lanzar la nueva excepción InvalidOperationException ("No se encontró el índice de inserción"); privado void Insert (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // actions // 1: Store index at temp temp = 4 // 2: establece el índice en para indexar desde -> 0 1 2 3 5 6 3 7 temp = 4 // 3: retrocediendo desde el índice desde hasta el índice en + 1. // Cambia los valores de izquierda a derecha una vez. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Escriba el valor de temp en el índice en + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Paso 1. T temp = itemArray [indexInsertingAt]; // Paso 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Paso 3. para (int current = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Paso 4. itemArray [indexInsertingAt + 1] = temp; | Comportamiento | Ordena la matriz de entrada usando el algoritmo de selección de selección. | ||
| Complejidad | Mejor caso | Caso medio | Peor de los casos |
| Hora | En) | En2) | En2) |
| Espacio | O (1) | O (1) | O (1) |
El tipo de selección es un tipo de híbrido entre el tipo de burbuja y el de inserción. Al igual que la ordenación por burbuja, procesa la matriz iterando de principio a fin una y otra vez, seleccionando un valor y moviéndolo a la ubicación correcta. Sin embargo, a diferencia del tipo de burbuja, elige el valor sin clasificar más pequeño en lugar del más grande. Al igual que la ordenación por inserción, la porción ordenada de la matriz es el comienzo de la matriz, mientras que con la ordenación por burbuja, la porción ordenada está al final.
Veamos cómo funciona esto usando la misma matriz sin clasificar que hemos estado usando.
Matriz sin clasificar de enteros En la primera pasada, el algoritmo intentará encontrar el valor más pequeño en la matriz y lo ubicará en el primer índice. Esto es realizado por el FindIndexOfSmallestFromIndex, que encuentra el índice del valor sin clasificar más pequeño comenzando en el índice proporcionado.
Con una matriz tan pequeña, podemos decir que el primer valor, tres, es el valor más pequeño por lo que ya está en el lugar correcto. En este punto, sabemos que el valor en el índice de matriz cero es el valor más pequeño y, por lo tanto, está en el orden correcto. Así que ahora podemos comenzar a pasar dos, esta vez solo mirando las entradas de la matriz uno a n-1.
La segunda pasada determinará que cuatro es el valor más pequeño en el rango sin clasificar, e intercambiará el valor en la segunda ranura con el valor en la ranura en la que se guardaron cuatro (intercambiando los cuatro y siete). Después de que se complete el paso dos, el valor cuatro se insertará en su posición ordenada.
Array después del segundo pase El rango ordenado ahora es del índice cero al índice uno, y el rango sin clasificar es del índice dos al n-1. A medida que termina cada paso subsiguiente, la parte ordenada de la matriz se hace más grande y la parte sin clasificar se hace más pequeña. Si en algún punto del camino no se realizan inserciones, se sabe que la matriz está ordenada. De lo contrario, el proceso continúa hasta que se sabe que toda la matriz está ordenada.
Después de dos pasadas más se ordena la matriz:
Matriz ordenada Public void Sort (T [] items) int sortedRangeEnd = 0; mientras < items.Length) int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) if (currentSmallest.CompareTo(items[i]) > 0) currentSmallest = items [i]; currentSmallestIndex = i; devolver currentSmallestIndex;
| Comportamiento | Ordena la matriz de entrada usando el algoritmo de ordenamiento de fusión. | ||
| Complejidad | Mejor caso | Caso medio | Peor de los casos |
| Hora | O (n log n) | O (n log n) | O (n log n) |
| Espacio | En) | En) | En) |
Hasta ahora hemos visto algoritmos que operan procesando linealmente la matriz. Estos algoritmos tienen la ventaja de operar con muy poca sobrecarga de memoria pero a costa de la complejidad de tiempo de ejecución cuadrática. Con la ordenación de fusión, vamos a ver nuestro primer algoritmo de dividir y conquistar.
Los algoritmos de dividir y conquistar funcionan dividiendo los problemas grandes en problemas más pequeños y más fáciles de resolver. Vemos estos tipos de algoritmos en la vida cotidiana. Por ejemplo, usamos un algoritmo de dividir y conquistar cuando buscamos en una guía telefónica..
Si quisiera encontrar el nombre de Erin Johnson en una guía telefónica, no comenzaría en A y voltearía página por página. Más bien, es probable que abra la guía telefónica al medio. Si abres a las M's, pasarías unas cuantas páginas, quizás un poco demasiado lejos, quizás las H's. Entonces te darías la vuelta. Y seguiría volteando de un lado a otro en incrementos cada vez más pequeños hasta que finalmente encontrara la página que quería (o estuviera tan cerca que tuviera sentido).
¿Cuán eficientes son los algoritmos de dividir y conquistar??
Digamos que la guía telefónica tiene 1000 páginas. Cuando abres al medio, has cortado el problema en dos problemas de 500 páginas. Suponiendo que no está en la página correcta, ahora puede elegir el lado apropiado para buscar y reducir el problema a la mitad nuevamente. Ahora su espacio problema es de 250 páginas. A medida que el problema se reduce a la mitad, podemos ver que una guía telefónica de 1000 páginas se puede buscar en solo diez giros. Esto es el 1% del número total de giros de página que podrían ser necesarios al realizar una búsqueda lineal.
La clasificación de fusión opera cortando la matriz por la mitad una y otra vez hasta que cada pieza tenga solo un elemento. Luego esos artículos se vuelven a juntar (combinados) en orden de clasificación.
Comencemos con la siguiente matriz:
Matriz sin clasificar de enteros Y ahora cortamos la matriz por la mitad:
Matriz sin clasificar cortada por la mitad Ahora, estas dos matrices se cortan por la mitad repetidamente hasta que cada elemento está solo:
Matriz sin clasificar cortada por la mitad hasta que cada índice esté por sí solo Con la matriz ahora dividida en las partes más pequeñas posibles, se produce el proceso de volver a unir esas partes en orden de clasificación..
Array clasificado en grupos de dos Los elementos individuales se convierten en grupos ordenados de dos, esos grupos de dos se combinan en grupos ordenados de cuatro, y finalmente todos se vuelven a unir como una matriz ordenada final.
Matriz clasificada en grupos de cuatro (arriba) y la clasificación completa (abajo) Tomemos un momento para pensar en las operaciones individuales que necesitamos implementar:
Ordenar método hace esto.Unir método hace esto.Una consideración de rendimiento de la ordenación de combinación es que, a diferencia de los algoritmos de ordenación lineal, la ordenación de combinación realizará toda su lógica de división y fusión, incluidas las asignaciones de memoria, incluso si la matriz ya está ordenada. Si bien tiene un mejor desempeño en el peor de los casos que los algoritmos de clasificación lineal, su mejor desempeño siempre será peor. Esto significa que no es un candidato ideal para clasificar los datos que se sabe que están casi ordenados; por ejemplo, al insertar datos en una matriz ya ordenada.
Public void Sort (T [] items) if (items.Length <= 1) return; int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); private void Merge(T[] items, T[] left, T[] right) int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) if (leftIndex> = left.Length) items [targetIndex] = right [rightIndex ++]; else if (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; else if (left [leftIndex] .CompareTo (right [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Comportamiento | Ordena la matriz de entrada usando el algoritmo de ordenamiento rápido. | ||
| Complejidad | Mejor caso | Caso medio | Peor de los casos |
| Hora | O (n log n) | O (n log n) | En2) |
| Espacio | O (1) | O (1) | O (1) |
La ordenación rápida es otra división y conquista del algoritmo de clasificación. Éste funciona realizando de forma recursiva el siguiente algoritmo:
Vamos a realizar una ordenación rápida en la siguiente matriz:
Matriz sin clasificar de enteros El primer paso dice que seleccionamos el punto de partición utilizando un índice aleatorio. En el código de ejemplo, esto se hace en esta línea:
int pivotIndex = _pivotRng.Next (izquierda, derecha);
Escoger un índice de partición aleatorio Ahora que conocemos el índice de partición (cuatro), observamos el valor en ese punto (seis) y movemos los valores en la matriz de modo que todo lo que es menor que el valor esté en el lado izquierdo de la matriz y todo lo demás (valores mayores que o igual) se mueve al lado derecho de la matriz. Tenga en cuenta que al mover los valores puede cambiar el índice en el que se almacena el valor de la partición (lo veremos en breve).
El intercambio de valores se realiza mediante el método de partición en el código de ejemplo.
Mover valores a la izquierda y derecha del valor de partición En este punto, sabemos que seis están en el lugar correcto en la matriz. Sabemos esto porque cada valor a la izquierda es menor que el valor de la partición, y todo a la derecha es mayor o igual al valor de la partición. Ahora repetimos este proceso en las dos particiones no clasificadas de la matriz.
La repetición se realiza en el código de ejemplo llamando recursivamente al método quicksort con cada una de las particiones de matriz. Observe que esta vez la matriz izquierda se divide en el índice uno con el valor cinco. El proceso de mover los valores a sus posiciones apropiadas mueve el valor cinco a otro índice. Señalo esto para reforzar el punto de que está seleccionando un valor de partición, no un índice de partición.
Repitiendo el pivote y la partición. Clasificación rápida de nuevo:
Repitiendo el pivote y la partición de nuevo. Y clasificación rápida una última vez:
Repitiendo el pivote y la partición de nuevo. Cuando solo queda un valor sin clasificar, y como sabemos que todos los demás valores están ordenados, la matriz está completamente ordenada.
Random _pivotRng = new Random (); Public void Sort (T [] items) quicksort (items, 0, items.Length - 1); Private Void Quicksort (T [] elementos, int izquierda, int derecha) if (izquierda < right) int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); private int partition(T[] items, int left, int right, int pivotIndex) T pivotValue = items[pivotIndex]; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) if (items[i].CompareTo(pivotValue) < 0) Swap(items, i, storeIndex); storeIndex += 1; Swap(items, storeIndex, right); return storeIndex;
