Sort Rápido vs Merge Sort en comparación

“El objetivo de este artículo es dar las similitudes y diferencias entre el tipo rápido y el tipo de fusión. El artículo "Sorteo rápido en C", o un título similar, ya ha sido escrito para Linuxhint.com/. El título se puede escribir en el cuadro de búsqueda del Linuxhint.com Página de inicio para llegar al artículo. Otro artículo, "Merge Sort in C", o un título similar, ya ha sido escrito para Linuxhint.com/. El título se puede escribir en el cuadro de búsqueda del Linuxhint.com Página de inicio para llegar al artículo. Se aconseja al lector que se refiera a esos dos artículos mientras él/ella lee este.

Quick Sort es un algoritmo de clasificación. Fusion Sort es otro algoritmo de clasificación. El código para los dos artículos mencionados anteriormente está escrito en c. El código para este artículo también está escrito en c. El lector debe ser consciente de eso. Se considera el ascendente de ascenso para ambos algoritmos de clasificación en este artículo."

Contenido del artículo

- Introducción - Ver arriba
- Algoritmos para clases rápidas y fusiones
- Big-o notación de o (n), o (n2) y o (n.registro (n))
- Comparación de clasificación rápida y fusión
- Conclusión

Algoritmos para clases rápidas y fusiones
Algoritmo para Quicksort

1) Si solo hay uno o ningún elemento en la lista, entonces regrese. Un elemento significa que la lista ya está ordenada. El elemento cero significa que no hay nada que clasificar.
2) Con una suposición inteligente, elija un elemento adecuado en la lista como un pivote.
3) Partición (dividir) la lista en tres subsists. Hacer todos los elementos para la subplaza izquierda menos que el pivote. La lista central tiene solo un elemento, que es el pivote. Haga que todos los elementos en la subplaza derecha sean más grandes que el pivote. Al poner elementos a la izquierda que son menos que el pivote, y elementos a la derecha que son mayores que el pivote, sin clasificación pura, que ya es una clasificación (en un sentido amplio).
4) Divida recursivamente cada subsist (izquierda y derecha) en tres, como en el paso anterior, con cada conjunto de tres subsistes que tienen su propio nuevo pivote (de una subsists de elementos), hasta que toda la lista dada es perfectamente ordenado.

Hay diferentes formularios de codificación para el paso 2. Un mejor formulario de codificación conducirá a una clasificación completa más rápida.
Hay diferentes formularios de codificación para el paso 3. Un mejor formulario de codificación conducirá a una clasificación completa más rápida.

Algoritmo para la combinación

1) Si solo hay uno o ningún elemento en la lista, entonces regrese. Un elemento significa que la lista ya está ordenada. El elemento cero significa que no hay nada que clasificar.
2) Divida recursivamente la lista y sus sub-listas en dos mitades hasta que cada subsist tenga solo un elemento.
3) Ordena pares de subsists de izquierda a derecha de forma recursiva, incluidos los pares más grandes resultantes, hasta que toda la lista esté recuperada pero completamente ordenada.

Esta es la forma normal de hacer Mergesort, y realmente no da espacio, para diferentes segmentos de código, para el mismo propósito que QuickSort.

Big-o notación de o (n), o (n2) y o (n.registro (n))

En)
Considere el siguiente código:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; isuma = suma + a [i];

printf ("%d \ n", suma);

n = 8. La salida, la suma es 36. En el for-bucle, hay una operación que se ejecuta 8 veces. En la notación Big-O, esta velocidad (complejidad del tiempo) se escribe como,

En)

Considere el siguiente código similar, donde solo se agregan los números impares:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; isuma = suma + a [i];

printf ("%d \ n", suma);

La salida, suma esta vez, es 16. En el for-bucle, la operación única se ejecuta 4 veces, que es n/2 veces. En la notación Big-O, esta velocidad (complejidad del tiempo) todavía se escribe como o (n). El número máximo de operaciones posibles es lo que se considera.

En²)

Considere el siguiente código que agrega la matriz de los números 8 por 8:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; ipara (int j = 0; jsum = suma + a [j];


printf ("%d \ n", suma);

La salida, la suma, es 288. En el for-bucle, hay una operación que se ejecuta 8 x 8 veces = 64 veces. En la notación Big-O, esta velocidad (complejidad del tiempo) se escribe como,

O (n²)

Considere el siguiente código similar, donde solo se agregan los números impares de la matriz:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; ipara (int j = 0; jsum = suma + a [j];


printf ("%d \ n", suma);

La salida, suma esta vez, es 64. En el bucle for-bucle, la operación se ejecuta 4 x 4 veces = 16 veces, que es n²/4 veces. Esto es más de 8 veces (más de n veces) pero menos de 64 veces (menos que n² veces). En la notación Big-O, esta velocidad (complejidad del tiempo) aún se puede escribir como o (n²). El número máximo de operaciones posibles es lo que se considera.

Aquí, no confunda la suma, 64, y el número de operaciones, 16. Este caso de 16 operaciones, entre 8 (n) y 64 (n²), todavía se puede escribir, como en la siguiente subsección.

En.registro (n))

Considere la situación de una matriz de 8 por 8, donde el número total de operaciones es 24. 24 puede verse como aproximadamente alrededor del medio, entre 8 (n) y 64 (n²).

Ahora,

24 = 8xlog₂(8)
=> 24 = 8xlog₂(2³)
=> 24 = 8 × 3

Ahora comparar,

24 = 8xlog₂(8)
con
24 = N.registro₂(norte)

Para el máximo de n², Cuando el número total de operaciones es entre n y n², y alrededor de su medio, en notación Big-O, esta velocidad (complejidad del tiempo) está mejor escrita como n.registro₂(n) en lugar de o (n²).

Comparación de clasificación rápida y fusión
Número de pasos en el algoritmo

Desde arriba, Quicksort tiene 4 pasos en su algoritmo, mientras que Mergesort tiene 3 pasos en su algoritmo.

Diferentes formas de codificación

El tipo rápido tiene diferentes formas de codificación, mientras que la clasificación de fusiones solo tiene una forma principal de codificación.

Complejidad del tiempo

La complejidad del tiempo para la combinación es n.registro₂(norte). Su velocidad es comparable a la de la función de clasificación de la biblioteca C ++ utilizada para fines comerciales.

Cuando la función de pivote mediana se usa para Quicksort, la complejidad del tiempo es de aproximadamente 1.188n.registro₂(n), más alto que se mergeort, suponiendo que se utilice una buena función de partición. Muchos programas de QuickSort tienen una mayor complejidad del tiempo. La peor complejidad del tiempo para QuickSort es O (n²). Sin embargo, si el programa QuickSort está bien codificado con muy buenos segmentos de código, superaría la combinación de la velocidad.

Conclusión

Quicksort normalmente funciona más lento que Mergesort.