shell sort c with examples
Técnica de clasificación de shell en C ++: una descripción completa.
La clasificación de shell se denomina a menudo como una mejora con respecto a la clasificación de inserción. En la ordenación por inserción, tomamos incrementos de 1 para comparar elementos y colocarlos en su posición correcta.
En la clasificación de shell, la lista se ordena dividiéndola en varias sublistas más pequeñas. No es necesario que las listas tengan elementos contiguos. En cambio, la técnica de ordenación de shell usa el incremento i, que también se llama 'espacio' y lo usa para crear una lista de elementos que son elementos 'i' aparte.
=> Consulte aquí para explorar la lista completa de tutoriales de C ++.
¿Cuál es la diferencia entre el reenvío de puertos y la activación de puertos?
Lo que vas a aprender:
Algoritmo general
El algoritmo general para la clasificación de shell se muestra a continuación.
ordenación_concha (A, N)
donde A - lista a ordenar; N - tamaño_pacho
establecer gap_size = N, flag = 1
mientras que gap_size> 1 o flag = 1, repita
comenzar
establecer bandera = 0
establecer gap_size = (gap_size + 1) / 2
fin
para i = 0 a i<(N-gap_size) repeat
comenzar
si A (i + tamaño_pacho)> A (i)
intercambiar A (i + gap_size), A (i)
establecer bandera = 0
fin
fin
Por lo tanto, en el algoritmo anterior, primero establecemos N, que es el espacio para ordenar la matriz A usando la clasificación de shell. En el siguiente paso, dividimos la matriz en submatrices usando el espacio. Luego, en el siguiente paso, ordenamos cada una de las submatrices de modo que al final del ciclo obtengamos una matriz ordenada.
A continuación, consideremos un ejemplo detallado para comprender mejor el tipo de caparazón utilizando una representación pictórica.
Ilustración
Ilustremos la ordenación de Shell con un ejemplo.
Considere la siguiente matriz de 10 elementos.
Si proporcionamos un espacio de 3, entonces tendremos las siguientes sublistas con cada elemento que está a 3 elementos de distancia. Luego clasificamos estas tres sublistas.
Las sublistas ordenadas y la lista resultante que obtenemos después de combinar las tres sublistas ordenadas se muestran a continuación.
La matriz anterior que hemos obtenido después de fusionar las submatrices ordenadas está casi ordenada. Ahora podemos realizar la ordenación por inserción en esta lista y ordenar toda la matriz. Este último paso se muestra a continuación para su referencia.
Como se vio anteriormente, después de realizar la clasificación de shell y fusionar las sublistas ordenadas, solo requerimos tres movimientos para ordenar completamente la lista. Por lo tanto, podemos ver que podemos reducir significativamente el número de pasos necesarios para ordenar la matriz.
La elección del incremento para crear sublistas es una característica única de la clasificación de shell.
Ejemplo de C ++
Veamos la implementación de la ordenación de shell en C ++ a continuación.
|_+_|Producción:
Matriz a ordenar:
45 23 53 43 18 24 8 95 101
Matriz después de ordenar el shell:
8 18 23 24 43 45 53 95 101
Hemos usado la misma lista que usamos en la ilustración y podemos ver que comenzamos inicialmente creando dos sublistas y luego reduciendo aún más la brecha. Una vez que se crean las sublistas según el espacio especificado, ordenamos cada una de las sublistas. Una vez ordenadas todas las sublistas, obtenemos la lista casi ordenada. Ahora, esta lista se puede ordenar usando el orden de inserción básico, que tomará muy pocos movimientos.
A continuación, implementemos la clasificación de shell utilizando el lenguaje Java.
Ejemplo de Java
|_+_|Producción:
Matriz a ordenar:
45 23 53 43 18 24 8 95 101
Matriz después de ordenar el shell:
8 18 23 24 43 45 53 95 101
Hemos implementado la misma lógica para la ordenación de shell en los programas C ++ y Java. Por lo tanto, como se explicó anteriormente en el programa Java, primero dividimos la matriz en submatrices y luego las clasificamos para obtener una matriz ordenada completa.
Conclusión
La ordenación de shell es el algoritmo altamente eficiente que mejora la ordenación por inserción.
Mientras que la ordenación por inserción funciona incrementando sus elementos en 1, la ordenación de shell usa el parámetro 'gap' para dividir la matriz en submatrices cuyos elementos están separados por 'gap'. Luego, podemos ordenar la lista individual usando la ordenación por inserción para obtener la matriz ordenada completa.
La ordenación de shell funciona más rápido que la ordenación por inserción y requiere menos movimientos para ordenar la matriz en comparación con la ordenación por inserción. Nuestro próximo tutorial explorará todo sobre la técnica de ordenación de montones para ordenar estructuras de datos.
=> Visite aquí para aprender C ++ desde cero.
Lectura recomendada
- Orden de selección en C ++ con ejemplos
- Método MongoDB Sort () con ejemplos
- Comando de ordenación de Unix con sintaxis, opciones y ejemplos
- Clasificación de burbujas en C ++ con ejemplos
- Orden de inserción en C ++ con ejemplos
- Combinar ordenación en C ++ con ejemplos
- Ordenar montón en C ++ con ejemplos
- Clasificación rápida en C ++ con ejemplos