introduction sorting techniques c
Lista de las diversas técnicas de clasificación en C ++.
La clasificación es una técnica que se implementa para organizar los datos en un orden específico. La clasificación es necesaria para garantizar que los datos que utilizamos estén en un orden particular para que podamos recuperar fácilmente la información requerida de la pila de datos.
Si los datos están descuidados y desordenados, cuando queremos un dato en particular, tendremos que buscarlo uno por uno cada vez para recuperar los datos.
=> Lea la serie de formación Easy C ++.
Por lo tanto, siempre es recomendable que mantengamos nuestros datos ordenados en un orden específico para que la recuperación de la información, así como otras operaciones realizadas sobre los datos, se puedan realizar de manera fácil y eficiente.
Almacenamos datos en forma de registros. Cada registro se compone de uno o más campos. Cuando cada registro tiene un valor único de un campo en particular, lo llamamos campo clave. Por ejemplo, en una clase, Roll No puede ser un campo único o clave.
cuál es la mejor cuenta de correo electrónico para tener
Podemos ordenar los datos en un campo clave en particular y luego ordenarlos en orden ascendente / creciente o en orden descendente / descendente.
De manera similar, en un diccionario telefónico, cada registro consta del nombre de una persona, dirección y número de teléfono. En este, el número de teléfono es un campo único o clave. Podemos ordenar los datos del diccionario en este campo telefónico. Alternativamente, también podemos ordenar los datos de forma numérica o alfanumérica.
Cuando podemos ajustar los datos para ordenarlos en la propia memoria principal sin necesidad de otra memoria auxiliar, lo llamamos como Clasificación interna .
Por otro lado, cuando necesitamos memoria auxiliar para almacenar datos intermedios durante la clasificación, llamamos a la técnica como Clasificación externa .
En este tutorial, aprenderemos las diversas técnicas de clasificación en C ++ en detalle.
Lo que vas a aprender:
Técnicas de clasificación en C ++
C ++ admite varias técnicas de clasificación que se enumeran a continuación.
Ordenamiento de burbuja
La clasificación de burbujas es la técnica más simple en la que comparamos cada elemento con su elemento adyacente e intercambiamos los elementos si no están en orden. De esta manera, al final de cada iteración (llamada pasada), el elemento más pesado aparece al final de la lista.
A continuación se muestra un ejemplo de clasificación de burbujas.
Matriz a ordenar:
Como se vio arriba, dado que es una matriz pequeña y casi estaba ordenada, logramos obtener una matriz completamente ordenada en unas pocas pasadas.
Implementemos la técnica Bubble Sort en C ++.
|_+_|Producción:
Lista de entrada…
10 2 0 43 12
Lista de elementos ordenados ...
0 2 10 12 43
Como se ve en el resultado, en la técnica de clasificación de burbujas, con cada pasada, el elemento más pesado se burbujea hasta el final de la matriz, clasificando así la matriz por completo.
Orden de selección
Es una técnica simple pero fácil de implementar en la que encontramos el elemento más pequeño de la lista y lo colocamos en su lugar adecuado. En cada pasada, se selecciona el siguiente elemento más pequeño y se coloca en su posición adecuada.
Tomemos la misma matriz que en el ejemplo anterior y realicemos el Orden de selección para ordenar esta matriz.
Como se muestra en la ilustración anterior, para N número de elementos, tomamos N-1 pasadas para ordenar completamente la matriz. Al final de cada pasada, el elemento más pequeño de la matriz se coloca en su posición correcta en la matriz ordenada.
A continuación, implementemos el Orden de selección usando C ++.
|_+_|Producción:
Ingrese la lista de elementos a ordenar
12 45 8 15 33
La lista ordenada de elementos es
8 12 15 33 45
En el ordenamiento por selección, con cada pasada, el elemento más pequeño de la matriz se coloca en su posición adecuada. Por lo tanto, al final del proceso de clasificación, obtenemos una matriz completamente ordenada.
Tipo de inserción
La ordenación por inserción es una técnica en la que partimos del segundo elemento de la lista. Comparamos el segundo elemento con su anterior (1S t) elemento y colóquelo en su lugar adecuado. En la siguiente pasada, para cada elemento, lo comparamos con todos sus elementos anteriores e insertamos ese elemento en su lugar correcto.
Las tres técnicas de clasificación anteriores son simples y fáciles de implementar. Estas técnicas funcionan bien cuando el tamaño de la lista es menor. A medida que la lista crece en tamaño, estas técnicas no funcionan de manera tan eficiente.
La técnica quedará clara al comprender la siguiente ilustración.
La matriz a ordenar es la siguiente:
Ahora, para cada pasada, comparamos el elemento actual con todos sus elementos anteriores. Así, en la primera pasada, comenzamos con el segundo elemento.
Por tanto, necesitamos N número de pasadas para ordenar completamente una matriz que contiene N número de elementos.
Implementemos la técnica de ordenación por inserción con C ++.
|_+_|Producción:
La lista de entrada es
12 4 3 1 15
La lista ordenada es
1 3 4 12 15
La salida anterior muestra la matriz ordenada completa usando la ordenación por inserción.
Ordenación rápida
Quicksort es el algoritmo más eficiente que se puede utilizar para ordenar los datos. Esta técnica utiliza la estrategia de 'divide y vencerás' en la que el problema se divide en varios subproblemas y, después de resolver estos subproblemas individualmente, se fusionan para obtener una lista ordenada completa.
En ordenación rápida, primero dividimos la lista alrededor del elemento pivote y luego colocamos los otros elementos en sus posiciones adecuadas de acuerdo con el elemento pivote.
Como se muestra en la ilustración anterior, en la técnica de ordenación rápida dividimos la matriz alrededor de un elemento de pivote de modo que todos los elementos menores que el pivote estén a su izquierda y cuáles de los mayores que el pivote estén a su derecha. Luego tomamos estas dos matrices de forma independiente y las clasificamos y luego las unimos o las conquistamos para obtener una matriz ordenada resultante.
La clave de Quicksort es la selección del elemento pivote. Puede ser el primero, el último o el elemento intermedio de la matriz. El primer paso después de seleccionar el elemento pivote es colocar el pivote en su posición correcta para que podamos dividir la matriz de manera apropiada.
Implementemos la técnica de clasificación rápida usando C ++.
|_+_|Producción:
Matriz de entrada
12 23 3 43 51
Matriz ordenada con Quicksort
3 12 23 43 51
En la implementación de ordenación rápida anterior, tenemos una rutina de partición que se usa para dividir la matriz de entrada alrededor de un elemento pivote que es el último elemento de la matriz. Luego llamamos a la rutina de ordenación rápida de forma recursiva para ordenar individualmente las submatrices como se muestra en la ilustración.
Combinar ordenar
Esta es otra técnica que utiliza la estrategia 'Divide y vencerás'. En esta técnica, dividimos la lista primero en mitades iguales. Luego, realizamos la técnica de combinación de clasificación en estas listas de forma independiente para que ambas listas estén ordenadas. Finalmente, fusionamos ambas listas para obtener una lista ordenada completa.
La clasificación por combinación y la clasificación rápida son más rápidas que la mayoría de las otras técnicas de clasificación. Su desempeño permanece intacto incluso cuando la lista crece en tamaño.
Veamos una ilustración de la técnica Merge Sort.
En la ilustración anterior, vemos que la técnica de ordenación por fusión divide la matriz original en subarreglos repetidamente hasta que solo hay un elemento en cada subarreglo. Una vez hecho esto, las submatrices se ordenan de forma independiente y se fusionan para formar una matriz ordenada completa.
A continuación, implementemos Merge Sort usando el lenguaje C ++.
|_+_|Producción:
Ingrese el número de elementos a ordenar: 5
Introduzca 5 elementos a ordenar: 10 21 47 3 59
Matriz ordenada
3 10 21 47 59
Tipo de concha
La clasificación de concha es una extensión de la técnica de clasificación por inserción. En la ordenación por inserción, solo nos ocupamos del siguiente elemento, mientras que, en la ordenación de shell, proporcionamos un incremento o un espacio mediante el cual creamos listas más pequeñas a partir de la lista principal. No es necesario que los elementos de las sublistas sean contiguos, sino que suelen estar separados por 'gap_value'.
La ordenación de shell funciona más rápido que la ordenación por inserción y requiere menos movimientos que la ordenación por inserción.
Si proporcionamos un espacio de, entonces tendremos las siguientes sublistas con cada elemento que está a 3 elementos de distancia.
Luego clasificamos estas tres sublistas.
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 matriz para ordenar toda la matriz.
Por lo tanto, vemos que una vez que dividimos la matriz en sublistas usando el incremento apropiado y luego las fusionamos, obtenemos la lista casi ordenada. La técnica de ordenación por inserción en esta lista se puede realizar y la matriz se ordena en menos movimientos que la ordenación por inserción original.
A continuación se muestra la implementación de Shell Sort en C ++.
|_+_|Producción:
Matriz a ordenar:
45 23 53 43 18
Matriz después de ordenar el shell:
18 23 43 45 53
Por tanto, la ordenación de shell actúa como una gran mejora sobre la ordenación por inserción y ni siquiera toma la mitad del número de pasos para ordenar la matriz.
Ordenar montón
Heapsort es una técnica en la que se utiliza la estructura de datos del montón (min-heap o max-heap) para ordenar la lista. Primero construimos un montón a partir de la lista sin clasificar y también usamos el montón para ordenar la matriz.
Heapsort es eficiente pero no tan rápido como el tipo Merge.
Como se muestra en la ilustración anterior, primero construimos un montón máximo a partir de los elementos de la matriz que se van a ordenar. Luego atravesamos el montón e intercambiamos el último y el primer elemento. En este momento, el último elemento ya está ordenado. Luego, nuevamente construimos un montón máximo con los elementos restantes.
De nuevo, recorra el montón e intercambie el primer y último elemento y agregue el último elemento a la lista ordenada. Este proceso continúa hasta que solo queda un elemento en el montón que se convierte en el primer elemento de la lista ordenada.
Implementemos ahora Heap Sort usando C ++.
|_+_|Producción:
Matriz de entrada
4 17 3 12 9
Matriz ordenada
3 4 9 12 17
Hasta ahora hemos discutido brevemente todas las principales técnicas de clasificación con una ilustración. Aprenderemos cada una de estas técnicas en detalle en nuestros tutoriales posteriores junto con varios ejemplos para comprender cada técnica.
Conclusión
La clasificación es necesaria para mantener los datos ordenados y ordenados. Sin clasificar y descuidado puede llevar más tiempo acceder y, por lo tanto, podría afectar el rendimiento de todo el programa. Por lo tanto, para cualquier operación relacionada con los datos, como el acceso, la búsqueda, la manipulación, etc., necesitamos que los datos estén ordenados.
Hay muchas técnicas de clasificación empleadas en programación. Cada técnica se puede emplear según la estructura de datos que estemos usando o el tiempo que tarda el algoritmo en ordenar los datos o el espacio de memoria que toma el algoritmo para ordenar los datos. La técnica que estamos usando también depende de la estructura de datos que estemos ordenando.
Las técnicas de clasificación nos permiten clasificar nuestras estructuras de datos en un orden específico y organizar los elementos en orden ascendente o descendente. Hemos visto las técnicas de clasificación como la clasificación de burbujas, clasificación de selección, clasificación de inserción, clasificación rápida, clasificación de shell, clasificación de fusión y clasificación de montón. La clasificación por burbujas y la clasificación por selección son más simples y fáciles de implementar.
En nuestros tutoriales posteriores, veremos en detalle cada una de las técnicas de clasificación mencionadas anteriormente.
=> Haga clic aquí para obtener el curso gratuito de C ++.
Lectura recomendada
- Ordenar montón en C ++ con ejemplos
- Combinar ordenación en C ++ con ejemplos
- Orden de inserción en C ++ con ejemplos
- Video 1 de JMeter: Introducción, descarga e instalación de JMeter
- Introducción al lenguaje de programación Java - Tutorial en vídeo
- Proceso de introducción e instalación de Python
- Comando de ordenación de Unix con sintaxis, opciones y ejemplos
- Método MongoDB Sort () con ejemplos