Fusionar ordenar en C
El programa Mergesort, escrito normalmente, es comparable (en términos de velocidad) a la función sort () proporcionada por C ++ en su biblioteca de algoritmo. Merge-sort también es un programa comercial de propósito general.
Este artículo explica cómo escribir el programa Mergesort en el idioma C.
Algoritmo de división y conquista, en su sentido amplio
En su sentido amplio, la matriz de elementos se divide en dos mitades: la mitad izquierda y la mitad derecha. Si el número total de elementos a ordenar es impar, entonces la mitad izquierda se hace más grande que la mitad derecha, por 1 unidad. De lo contrario, ambas mitades son de la misma longitud. Las dos mitades se fusionan mientras se clasifican para formar una matriz ordenada. La fusión/clasificación está conquistando. Considere que se ordenen los siguientes caracteres:
P W E R T Y U I O PDividir este conjunto de caracteres alfabéticos en dos mitades, da:
P W E R T Y U I O PUna subcuenca se llama correr. Entonces, la subconjunto de la izquierda, "Q W e r t" es una ejecución y la submarina derecha, "y u i o p" es también una carrera. Una carrera también puede tener solo un elemento.
Fusionar/clasificar (conquistar) Ambas mitades en un conjunto da:
E i o p q r t u w yEl código para dividir por 2 es:
int imiddle = (ibegin + iend) / 2;Esta es la división entera. Entonces, se toma la parte del número entero del resultado. Con esto, si el número total de elementos en el conjunto es impar, la mitad izquierda sería mayor que la mitad derecha, por 1 unidad para la indexación basada en cero.
Para la declaración anterior y el conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', Ibegin = 0, IEND = 10 (que es el último índice de 9, más 1), imiddle = 5;
El código para fusionar/ordenar (conquistar) es:
int i = ibegin;int j = imiddle;
para (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
demás
Q [k] = p [j];
j = j + 1;
P es la matriz dada. Q tendría la matriz ordenada, en este caso.
Si este código se aplica al conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p' , habrá fusiones de las mitades divididas, pero no hay clasificación (porque cada elemento en la carrera izquierda es menor que 'y'). Este código se revisa a continuación para mostrar su efectividad en la clasificación de un par consecutivo de carreras.
Algoritmo práctico de división y conquista
Todo el programa Mergesort se puede escribir de arriba hacia abajo o de abajo hacia arriba. En este artículo, el programa está escrito, de arriba hacia abajo.
Un Mergesort opera conceptualmente de la siguiente manera:
1) Divida el conjunto sin clasificar en n subconjuntos (ejecuciones), donde cada uno tiene un elemento. Tenga en cuenta que un conjunto con solo un elemento se considera ordenado.
2) Fusionar repetidamente subconjuntos para obtener nuevos subconjuntos clasificados, hasta que solo quede un subconjunto. Este es el conjunto ordenado.
Con estos dos puntos, un set sin clasificación dado se divide en dos carreras. Cada una de estas dos ejecuciones se registra en la memoria para fusionar/clasificar juntos, pero aún no se fusionan. Cada carrera de nuevo a cada lado, se divide en dos. Los pares consecutivos de carreras se registran para fusionar/clasificar juntos, pero aún no se fusionan o se clasifican todavía. Esta división en dos y la grabación para fusionar/clasificar los pares consecutivos se repite hasta que solo haya un elemento por ejecución.
La grabación en la memoria para fusionar/clasificar juntas de ejecuciones consecutivas se realiza llamando al código de clasificación anterior de forma recursiva después de la división. El código de clasificación está en una función separada. La declaración de división y la llamada de la función de clasificación (que también se fusiona) está en un segmento de código (una función) con la declaración de división escrita primero.
Cuando la división ha llegado al estado de las ejecuciones de un solo elemento, las funciones de fusión/clasificación registradas en la memoria se llaman en orden inverso en el que se registraron. Es una función de fusión/clasificación que se registró en la memoria muchas veces con diferentes argumentos. Los pares consecutivos de elementos individuales se ordenan primero, fusionándose al mismo tiempo. La clasificación y la fusión de las corridas consecutivas continúan hasta que se ordene todo el conjunto. Entonces, la clasificación no está realmente en la disposición de los elementos como se dio originalmente.
En C, existe la necesidad de una segunda matriz, cuya longitud es tan larga como la matriz dada. Inicialmente, todos los elementos para esta segunda matriz deben hacerse, el valor predeterminado del tipo de datos. Los elementos de la matriz dada se clasifican en esta segunda matriz. Luego copió de nuevo a la matriz dada, anulando los elementos sin clasificar.
Para los personajes, esta segunda matriz se puede crear e inicializar de la siguiente manera:
char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';int sz = sizeof (p)/sizeof (p [0]);
char q [sz];
para (int i = 0; i
Aquí, la matriz dada es P, y la segunda matriz es Q. Este código puede estar en la función principal. En C/C ++, el carácter predeterminado es "y no un espacio ("). Sin embargo, dado que el compilador G ++ no permitiría la asignación de "a Q [i], se asignó el espacio único (").
Tenga en cuenta que los valores predeterminados para los elementos de matriz Q no son realmente necesarios para el programa completo de Mergesort, ya que los elementos de interés aún los anulan. Declarando la matriz Q con su tamaño, sz es suficiente.
El conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', se usa para explicar cómo se logra prácticamente la combinación, en esta sección. Dar la matriz Q valores predeterminados se ha enseñado en este artículo como conocimiento adicional.
El conjunto se divide en los dos conjuntos:
'Q', 'W', 'e', 'r', 't' y 'y', 'u', 'i', 'o', 'p'El código de fusión/clasificación anterior se llama como una función, pero la clasificación y la fusión no tienen lugar. En el programa real, la clasificación y la fusión de estas dos ejecuciones se registran en la memoria, primero. La clasificación y la fusión no necesariamente se realizarán en estos dos disposiciones particulares de personajes.
Los dos subconjuntos anteriores están cada uno, más divididos en dos para tener:
'Q', 'W', 'E' y 'r', 't' y 'y', 'u', 'i' y 'o', 'p'Tenga en cuenta que para cada nueva división aquí, el subconjunto izquierdo es más largo que el subconjunto derecho por una unidad.
El código de fusión/clasificación anterior se llama como una función, para pares consecutivos de estos nuevos subconjuntos. Pero la clasificación y la fusión no se lleva a cabo de inmediato. La clasificación y la fusión de estos pares consecutivos de ejecuciones se registran en la memoria de la computadora. La clasificación y la fusión no se hará necesariamente, en la disposición particular de los caracteres de estos pares consecutivos de carreras.
Los subconjuntos anteriores están cada uno, divididos en dos para tener:
'Q', 'W' y 'e' y 'r' y 't' y 'y', 'u' y 'i' y 'o' y 'PAG'Se registra la clasificación y la fusión de pares consecutivos.
Aquí, algunos subconjuntos no se pueden dividir más porque cada uno consiste en un elemento. Luego, la división de los subconjuntos de más de una longitud arriba, conduce a:
'Q' y 'w' y 'e' y 'r' y 't' y 'y' y 'u' y 'i' y ' O ' y ' P 'Se registra la clasificación y la fusión de pares consecutivos.
La función de clasificación y fusión se codifica de manera recursiva. Y así, se llamará en el orden invertido, para muchas veces, se registró.
Entonces, 'Q' y 'w' se clasificarán y se fusionarán en 'Q', 'W'. 'E' y 'r' se clasificarán y se fusionarán en 'e', 'r'. 'T'. 'Y' se ordenará y se fusionará en 't', 'y'. 'U' y 'i' se clasificará y se fusionará en 'i', 'u'. 'O'. 'P' se ordenará y se fusionará en 'O', 'P'. La función de fusión y clasificación anterior se usa aquí; y se usa en todo.
Siguiente: 'Q', 'W' y 'e', 'r' se clasificará y se fusionará en 'e', 'q', 'r', 'w'. 'T', 'y' y 'i', 'u' se clasificará y se fusionará en, 'i', 't', 'u', 'y'. En esta etapa, 'O', 'P' no se une a ningún subconjunto anterior de dos. La función de fusión y clasificación anterior se ha utilizado aquí y se usa en todo.
La siguiente etapa: 'e', 'q', 'r', 'w' y 'i', 't', 'u', 'y' se clasifican y se fusionan en 'e', ' I ',' q ',' r ',' t ',' u ',' w ',' y '. En esta etapa, 'o', 'p' nuevamente no se une a ninguno de los subconjuntos anteriores.
La última etapa: 'e', 'i', 'q', 'r', 't', 'u', 'w', 'y' y 'o', p ' se clasifican y se fusionan en 'e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y'. El conjunto no organizado ha sido ordenado.
Codificación de mersort en c
La tarea es clasificar la matriz P y no la matriz q. Entonces, para todo el programa Mergesort, Array Q se hace por primera vez una copia de Array P. El programa luego clasifica la matriz Q en la matriz P. Esto no es exactamente lo que está insinuado arriba. Hay cuatro funciones para el programa completo de Mergesort.
La función de dividir y fusionar
Esta es la función principal en el programa. Recuerde que la fusión también implica la clasificación de las carreras consecutivas izquierda y derecha. Esta fusión está en memoria y en realidad comienza cuando la matriz se ha dividido por dos y dos, etc. Hasta que solo haya un elemento por carrera. Entonces, la clasificación y la fusión comienza en esa etapa con un par para un elemento por carrera. El esqueleto de la función de clasificación es:
void topdownsplitmerge (char q [], int iBegin, int iend, char p [])| |
// Divide el subconjunto de más de 1 elemento en dos
int imiddle = (ibegin + iend) / 2; // imiddle es el punto medio
| |
| |
| |
// fusionar los subconjuntos resultantes de la matriz q [] en p []
Topdownmerge (Q, Ibegin, Imiddle, Iend, P);
Esta función toma la matriz dada como Q, que en este caso es en realidad la matriz de copias Q. También toma la matriz de copias como P, que en este caso es en realidad la matriz dada P. Para la primera llamada de esta función, ibegin = 0 e Iend = n, donde n es el tamaño de ambas matrices. Estos se deben al empleo de la matriz de índice cero.
Después de una división por dos, Ibegin será el primer índice de la ejecución de la izquierda y IEND será el último índice de la carrera derecha consecutiva. La división de dos le da al entero, imiddle, ignorando el resto. Este es el último índice de la ejecución de la izquierda y también el primer índice de la ejecución derecha. Esta ambigüedad es eliminada por la condición del tiempo del código de clasificación.
La última declaración en el código anterior es una llamada a la función precisa de fusión y clasificación. Esta llamada va a la memoria, cuando se llama. Se ejecutará en orden invertido para todas sus llamadas porque es una llamada recursiva. Toma las variables como argumentos. Q, Ibegin, Iend y P, recibidos por la función codificada externa. Imiddle, que también es uno de sus argumentos, se crea dentro de la función codificada externa, por encima de la llamada.
Está dentro de esta función codificada externa que las ejecuciones izquierda y derecha deben identificarse (dividirse). Esto se hace mejor haciendo una llamada recursiva a la función codificada externa de la siguiente manera (algún código incluido en la definición de funciones):
void topdownsplitmerge (char q [], int iBegin, int iend, char p [])// Divide el subconjunto de más de 1 elemento en dos
int imiddle = (ibegin + iend) / 2; // imiddle es el punto medio
// clasifica recursivamente ambas ejecuciones desde la matriz A [] en B []
topdownsplitmerge (p, ibegin, imiddle, q); // divide el subconjunto izquierdo en dos para clasificar, después de la memorización
topdownsplitmerge (p, imiddle, ieend, q); // Divide el subconjunto derecho en dos para clasificar, después de la memorización
// fusionar los subconjuntos resultantes de la matriz q [] en p []
Topdownmerge (Q, Ibegin, Imiddle, Iend, P);
Las dos nuevas llamadas recursivas se han escrito por encima de la llamada recursiva de TopdownMerge (). Estas dos llamadas serán memorizadas junto con TopdownMerge () y llamadas tantas veces como sea necesario, cada una en orden inverso.
Si la matriz dada no tiene elemento, no debe haber clasificación. Si el número de elementos en la matriz dada es 1, entonces la matriz ya está ordenada y no debe realizarse ninguna clasificación. Esto se atiende por una declaración en el interior, pero en la parte superior de la función codificada externa, TopdownsplitMerge () como sigue:
void topdownsplitmerge (char q [], int iBegin, int iend, char p [])if (Iend - Ibegin<= 1)
devolver;
int imiddle = (ibegin + iend) / 2;
topdownsplitmerge (p, ibegin, imiddle, q);
topdownsplitmerge (p, imiddle, ieend, q);
Topdownmerge (Q, Ibegin, Imiddle, Iend, P);
La función precisa para fusionar y ordenar
El nombre de esta función es topdownmerge (). Se llama recursivamente por topdownsplitmerge (). El código es:
void topdownmerge (char p [], int ibegin, int imiddle, int iend, char q [])// Mientras hay elementos en los subconjuntos izquierdo o derecho ..
int i = ibegin;
int j = imiddle;
para (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
demás
Q [k] = p [j];
j = j + 1;
En teoría, esta función itera desde el comienzo de la ejecución izquierda (subconjunto) hasta el final de la ejecución derecha (subconjunto). Observe cómo la ambigüedad mencionada anteriormente ha sido atendida por la condición de la construcción de IF.
Haciendo una copia única para todos los elementos
Al comienzo del programa, después de la siguiente función (esta sección), se ha llamado, todos los elementos de la matriz dada deben copiarse en la matriz, Q. El código para eso es:
nulo copyArray (char p [], int iBegin, int iend, char q [])para (int i = ibegin; i
Se llama una vez desde la siguiente función. Esto toma como argumentos, la matriz dada, p, entonces 0, entonces n y la otra matriz q, que está en teoría vacía pero ya tiene el mismo número de elementos que P. Iend, que es lo mismo que n, aquí, es la longitud de la matriz originalmente dada.
Función para iniciar el programa
La función para iniciar el programa es:
void topdownmerGesort (char p [], char q [], int n)copyArray (p, 0, n, q); // p [] se copia a Q [] una vez
topdownsplitmerge (Q, 0, n, p);
Llama a la función copyArray (), con los argumentos esperados. A continuación, llama la función principal, TopDownsPlitMerge (), con las posiciones de las matrices, P y Q, intercambiadas. Es por eso que, en el código TopdownMerge (), los valores ordenados se envían a Q y no a P.
Arreglo de código
Si las cuatro funciones codificadas anteriores se escriben en el siguiente orden,
- void topdownmerge ()
- void topdownsplitmerge ()
- copyArray ()
- topdownmerGesort ()
entonces el programa Mergesort (que consiste principalmente en estas cuatro funciones) funcionará en un compilador C sin ningún problema.
C Función principal
Una función principal C adecuada para este programa es:
int main (int argc, char ** argv)char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';
int sz = sizeof (p)/sizeof (p [0]);
char q [sz];
para (int i = 0; i
TopdownMergesort (P, Q, SZ);
para (int i = 0; i
printf ("\ n");
regresar 0;
Conclusión
Divide y conquistar el algoritmo divide el problema en piezas más pequeñas, con la esperanza de resolverlos de forma independiente. Después de que se han resuelto todas las piezas más pequeñas, sus soluciones se combinan en una solución principal. Con fusión de fusión, hay una división continua por dos, hasta que cada subconjunto sea un elemento largo y automáticamente ya ordenado. Unir estos elementos individuales se ejecuta, implica funciones recursivas y clasificación real, comenzando con pares de elementos individuales.