Complejidad de tiempo de clasificación rápida
Ahora, hay diferentes formas de escribir las funciones Pivot () y Particition (). La elección del tipo de función Pivot () y/o partición () determina la eficiencia de todo el programa. La eficiencia es como el número de operaciones principales que realizan el programa.
La complejidad del tiempo es el tiempo de ejecución relativo de un programa. Esto puede verse como la operación principal del programa.
La clasificación puede ser ascendente o descendente. En este artículo, la clasificación es ascendente.
El objetivo de este artículo es producir la complejidad del tiempo para un programa QuickSort. Dado que QuickSort se puede escribir de diferentes maneras dependiendo de la elección de las funciones PIVOT () y/o Partition (), cada tipo de clasificación rápida tiene su propia complejidad de tiempo. Sin embargo, hay una variedad de una serie de operaciones en las que se ajustan los diferentes tipos de programas de QuickSort. Este artículo presenta solo uno de los diferentes tipos de programas de QuickSort. Cualquier segmento de código presentado es del idioma C.
División entera por dos
Quick Sort usa la división entera para dividir su conjunto principal en conjuntos más pequeños.
Ahora,
11/2 = 5 resto 1
La división entera significa, tomar 5 y abandonar 1. Es decir, acepte el número entero e ignore el resto.
También,
10/2 = 5 resto 0
Aquí, el resto es cero y no importa. Aún así, la división Integer toma 5 y abandona 0. Es decir, acepte el número entero e ignore el resto que esté allí, incluso si es cero. A veces en la programación, también es bueno saber si el resto es 0 o no, ver más tarde.
Al dividir una lista en el sesiones rápidas, la división entera es lo que se usa.
Para un orden rápido, para obtener el índice medio basado en cero para una lista, do la división entera por dos para la longitud de la lista. El número completo es el índice medio basado en cero. Para obtener la longitud de la lista, comience a contar desde 1.
Complejidad del tiempo relacionada con el tipo rápido
Considere el siguiente código:
int n = 8;char a [] = 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h';
para (int i = 0; i
printf ("\ n");
La salida es:
a b c d e f g hEs decir, los ocho elementos han sido impresos.
Hay ocho elementos identificados por n. El cuerpo del bucle tiene un contenido.
printf ("%c", a [i]);Esta es una operación principal. Entonces, ocho operaciones principales han tenido lugar. La complejidad del tiempo para este código se escribe como:
En)
Donde n es el número de operaciones principales. Esta es la notación Big-O. En la notación, la primera carta está en mayúscula. Luego hay paréntesis. Dentro de los paréntesis es el número de operaciones o el máximo número posible de operaciones.
Ahora considere el siguiente segmento de código:
para (int i = 0; i<8; i++)para (int i = 0; i
if (i == 2)
romper;
printf ("\ n");
La salida es:
a B CEl cuerpo del bucle tiene un contenido.
printf ("%c", a [i]);if (i == 2)
romper;
Esta todavía se considera una operación principal en esta situación. Se han imprimido tres elementos porque la operación principal se ha ejecutado tres veces.
Ahora,
8 = 23
=> 3 = registro2(8)
Si 8 es n, entonces 3 es,
registro2(norte)
Y la complejidad del tiempo se daría como:
O (registro2norte)
Todavía hay otro segmento de código que considerar en relación con la complejidad del tiempo de QuickSort. Es
para (int i = 0; iprintf ("\ n");
printf ("\ n");
La salida es:
a b c d e f g ha b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
El número de caracteres impresos es 64, desde un número inicial de 8. Esto significa que la operación principal se ha ejecutado 64 veces.
64 = 8 x 8 = 82
Si 8 es n, entonces esto sería n2. La complejidad del tiempo para este código es:
En2)
Algoritmo de clasificación rápida en este artículo
Para este artículo, los pasos del algoritmo son:
- Busque la mediana (ver más abajo) entre el primer elemento, el elemento medio y el último elemento de la lista.
- Colocar la mediana en el medio de la lista.
- Envíe todos los elementos a la derecha que son menos que la mediana, ahora en el medio, a la izquierda de la mediana, y envíe todos los elementos a la izquierda que son mayores que la mediana a la derecha de la mediana. Esto se llama partición.
- Repita los tres pasos anteriores en orden, para cada subsist, hasta que la lista se haya separado en elementos individuales.
- Cuando la lista consta de elementos individuales separados, la lista está ordenada.
Mediana
Para obtener la mediana de los tres elementos,
TAXIreorganizar los tres elementos en orden, yo.mi.
A B CEl elemento medio, b, es la mediana.
Ilustración de clasificación rápida
La lista a ordenar es:
P V D Q S X T BHay ocho elementos. Cuando la lista ha sido ordenada, sería:
B D P Q S T V XEntonces, el problema es: ordenar la lista:
P V D Q S X T BUsando Quicksort.
La mediana entre P, Q y B se busca. Es p. Esta búsqueda de la mediana implica tres operaciones. Entonces, hay un total de tres operaciones hasta ahora. Poner la mediana en el medio de la lista da:
V D Q P S X T BRecuerde: el índice para el elemento medio es el resultado de la división entera por dos. Hay cuatro movimientos aquí, para P y Q. Esas son cuatro operaciones. Eso hace un total de siete operaciones hasta ahora (tres más cuatro). Ahora, B se enviará a la izquierda, y V y Q serán enviados a la derecha para tener:
D B P V Q S X TTenga en cuenta que P ya no está en el verdadero medio. Sin embargo, hubo tres movimientos. Estas son tres operaciones. Entonces hay diez operaciones hasta ahora (siete más tres). Cada una de las dos subsistes debe dividirse en tres partes (la mediana es una parte).
La mediana para D y B es D. La búsqueda de la mediana son tres operaciones. Eso hace un total de trece operaciones hasta ahora (diez más tres). La partición de estos elementos da:
B DHubo dos movimientos aquí. Esas son dos operaciones. Esto hace un total de quince operaciones hasta ahora (trece más dos). A continuación, la mediana para el conjunto V, Q, S, X, T debe ser buscada, y el set dividido.
La mediana para V, S y T es T. La búsqueda mediana son tres operaciones. Hasta ahora, ha habido dieciocho operaciones (quince más tres). Poner t en el medio da:
V Q T S XHay tres movimientos aquí. Estas son tres operaciones. El número total de operaciones hasta ahora es veintiún (dieciocho más tres). Enviar elementos más bajos a la derecha de t a la izquierda, y elementos más altos a la izquierda de T a la derecha, da:
Q S T V XHay dos movimientos aquí. Estas son dos operaciones. Hasta ahora, hay un total de veintitrés operaciones (veintiún dos). Poner todas las particiones hasta ahora da:
B D P Q S T V XObserve que la lista ya está ordenada. Sin embargo, el algoritmo tiene que terminar. Q, s y v, x tienen que ser atendidos a. No habrá movimiento de personajes entre estos dos. Sin embargo, su mediana será vista a. La búsqueda de dos medianas es de seis operaciones. Esto hace un total de veintinueve operaciones para todo el programa (veintitrés más seis). La lista final ordenada es:
B D P Q S T V XNota:
24 = 8 x 3
=> 24 = 8xlog28
29 es aproximadamente igual a 24.
Conclusión
Dependiendo del tipo de función elegida para pivot () y el tipo de función elegida para la partición (), la complejidad del tiempo para el programa QuickSort estará en algún lugar entre
En.registro2norte)
y
En2)
inclusivo. Tenga en cuenta que el punto en o (n.registro2n) significa multiplicación.